diff options
Diffstat (limited to 'plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java')
-rw-r--r-- | plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java | 1087 |
1 files changed, 1087 insertions, 0 deletions
diff --git a/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java new file mode 100644 index 000000000000..6198da1b21bf --- /dev/null +++ b/plugins/java-decompiler/engine/src/org/jetbrains/java/decompiler/modules/decompiler/FinallyProcessor.java @@ -0,0 +1,1087 @@ +/* + * Copyright 2000-2014 JetBrains s.r.o. + * + * Licensed under the Apache License, Version 2.0 (the "License"); + * you may not use this file except in compliance with the License. + * You may obtain a copy of the License at + * + * http://www.apache.org/licenses/LICENSE-2.0 + * + * Unless required by applicable law or agreed to in writing, software + * distributed under the License is distributed on an "AS IS" BASIS, + * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied. + * See the License for the specific language governing permissions and + * limitations under the License. + */ +package org.jetbrains.java.decompiler.modules.decompiler; + +import org.jetbrains.java.decompiler.code.*; +import org.jetbrains.java.decompiler.code.cfg.BasicBlock; +import org.jetbrains.java.decompiler.code.cfg.ControlFlowGraph; +import org.jetbrains.java.decompiler.code.cfg.ExceptionRangeCFG; +import org.jetbrains.java.decompiler.main.DecompilerContext; +import org.jetbrains.java.decompiler.main.collectors.CounterContainer; +import org.jetbrains.java.decompiler.main.extern.IFernflowerPreferences; +import org.jetbrains.java.decompiler.modules.code.DeadCodeHelper; +import org.jetbrains.java.decompiler.modules.decompiler.exps.AssignmentExprent; +import org.jetbrains.java.decompiler.modules.decompiler.exps.ExitExprent; +import org.jetbrains.java.decompiler.modules.decompiler.exps.Exprent; +import org.jetbrains.java.decompiler.modules.decompiler.exps.VarExprent; +import org.jetbrains.java.decompiler.modules.decompiler.sforms.DirectGraph; +import org.jetbrains.java.decompiler.modules.decompiler.sforms.DirectNode; +import org.jetbrains.java.decompiler.modules.decompiler.sforms.FlattenStatementsHelper; +import org.jetbrains.java.decompiler.modules.decompiler.sforms.SSAConstructorSparseEx; +import org.jetbrains.java.decompiler.modules.decompiler.stats.BasicBlockStatement; +import org.jetbrains.java.decompiler.modules.decompiler.stats.CatchAllStatement; +import org.jetbrains.java.decompiler.modules.decompiler.stats.RootStatement; +import org.jetbrains.java.decompiler.modules.decompiler.stats.Statement; +import org.jetbrains.java.decompiler.modules.decompiler.vars.VarProcessor; +import org.jetbrains.java.decompiler.modules.decompiler.vars.VarVersionPaar; +import org.jetbrains.java.decompiler.struct.StructMethod; +import org.jetbrains.java.decompiler.struct.gen.VarType; +import org.jetbrains.java.decompiler.util.InterpreterUtil; + +import java.util.*; +import java.util.Map.Entry; + +public class FinallyProcessor { + + private Map<Integer, Integer> finallyBlockIDs = new HashMap<Integer, Integer>(); + private Map<Integer, Integer> catchallBlockIDs = new HashMap<Integer, Integer>(); + + private VarProcessor varprocessor; + + public FinallyProcessor(VarProcessor varprocessor) { + this.varprocessor = varprocessor; + } + + public boolean iterateGraph(StructMethod mt, RootStatement root, ControlFlowGraph graph) { + // return processStatement(mt, root, graph, root); + return processStatementEx(mt, root, graph); + } + + private boolean processStatementEx(StructMethod mt, RootStatement root, ControlFlowGraph graph) { + + int bytecode_version = mt.getClassStruct().getBytecodeVersion(); + + LinkedList<Statement> stack = new LinkedList<Statement>(); + stack.add(root); + + while (!stack.isEmpty()) { + + Statement stat = stack.removeLast(); + + Statement parent = stat.getParent(); + if (parent != null && parent.type == Statement.TYPE_CATCHALL && + stat == parent.getFirst() && !parent.isCopied()) { + + CatchAllStatement fin = (CatchAllStatement)parent; + BasicBlock head = fin.getBasichead().getBlock(); + BasicBlock handler = fin.getHandler().getBasichead().getBlock(); + + if (catchallBlockIDs.containsKey(handler.id)) { + // do nothing + } + else if (finallyBlockIDs.containsKey(handler.id)) { + + fin.setFinally(true); + + Integer var = finallyBlockIDs.get(handler.id); + fin.setMonitor(var == null ? null : new VarExprent(var.intValue(), VarType.VARTYPE_INT, varprocessor)); + } + else { + + Record inf = getFinallyInformation(mt, root, fin); + + if (inf == null) { // inconsistent finally + catchallBlockIDs.put(handler.id, null); + } + else { + + if (DecompilerContext.getOption(IFernflowerPreferences.FINALLY_DEINLINE) && verifyFinallyEx(graph, fin, inf)) { + finallyBlockIDs.put(handler.id, null); + } + else { + + int varindex = DecompilerContext.getCounterContainer().getCounterAndIncrement(CounterContainer.VAR_COUNTER); + insertSemaphore(graph, getAllBasicBlocks(fin.getFirst()), head, handler, varindex, inf, bytecode_version); + + finallyBlockIDs.put(handler.id, varindex); + } + + DeadCodeHelper.removeDeadBlocks(graph); // e.g. multiple return blocks after a nested finally + DeadCodeHelper.removeEmptyBlocks(graph); + DeadCodeHelper.mergeBasicBlocks(graph); + } + + return true; + } + } + + stack.addAll(stat.getStats()); + } + + return false; + } + + + // private boolean processStatement(StructMethod mt, RootStatement root, ControlFlowGraph graph, Statement stat) { + // + // boolean res = false; + // + // for(int i=stat.getStats().size()-1;i>=0;i--) { + // if(processStatement(mt, root, graph, stat.getStats().get(i))) { + // return true; + // } + // } + // + // + // if(stat.type == Statement.TYPE_CATCHALL && !stat.isCopied()) { + // + // CatchAllStatement fin = (CatchAllStatement)stat; + // BasicBlock head = fin.getBasichead().getBlock(); + // BasicBlock handler = fin.getHandler().getBasichead().getBlock(); + // + // if(catchallBlockIDs.containsKey(handler.id)) { + // ; // do nothing + // }else if(finallyBlockIDs.containsKey(handler.id)) { + // + // fin.setFinally(true); + // + // Integer var = finallyBlockIDs.get(handler.id); + // fin.setMonitor(var==null?null:new VarExprent(var.intValue(), VarType.VARTYPE_INT, varprocessor)); + // + // } else { + // + // Object[] inf = getFinallyInformation(mt, root, fin); + // + // if(inf == null) { // inconsistent finally + // catchallBlockIDs.put(handler.id, null); + // } else { + // + // if(DecompilerContext.getOption(IFernflowerPreferences.FINALLY_DEINLINE) && verifyFinallyEx(graph, fin, inf)) { + // finallyBlockIDs.put(handler.id, null); + // } else { + // + // int varindex = DecompilerContext.getCountercontainer().getCounterAndIncrement(CounterContainer.VAR_COUNTER); + // insertSemaphore(graph, getAllBasicBlocks(fin.getFirst()), head, handler, varindex, inf); + // + // finallyBlockIDs.put(handler.id, varindex); + // } + // + // DeadCodeHelper.removeEmptyBlocks(graph); + // DeadCodeHelper.mergeBasicBlocks(graph); + // } + // + // res = true; + // } + // } + // + // return res; + // } + + private static class Record { + private final int firstCode; + private final Map<BasicBlock, Boolean> mapLast; + + private Record(int firstCode, Map<BasicBlock, Boolean> mapLast) { + this.firstCode = firstCode; + this.mapLast = mapLast; + } + } + + + private static Record getFinallyInformation(StructMethod mt, RootStatement root, CatchAllStatement fstat) { + + Map<BasicBlock, Boolean> mapLast = new HashMap<BasicBlock, Boolean>(); + + BasicBlockStatement firstBlockStatement = fstat.getHandler().getBasichead(); + BasicBlock firstBasicBlock = firstBlockStatement.getBlock(); + Instruction instrFirst = firstBasicBlock.getInstruction(0); + + int firstcode = 0; + + switch (instrFirst.opcode) { + case CodeConstants.opc_pop: + firstcode = 1; + break; + case CodeConstants.opc_astore: + firstcode = 2; + } + + ExprProcessor proc = new ExprProcessor(); + proc.processStatement(root, mt.getClassStruct()); + + SSAConstructorSparseEx ssa = new SSAConstructorSparseEx(); + ssa.splitVariables(root, mt); + + List<Exprent> lstExprents = firstBlockStatement.getExprents(); + + VarVersionPaar varpaar = new VarVersionPaar((VarExprent)((AssignmentExprent)lstExprents.get(firstcode == 2 ? 1 : 0)).getLeft()); + + FlattenStatementsHelper flatthelper = new FlattenStatementsHelper(); + DirectGraph dgraph = flatthelper.buildDirectGraph(root); + + LinkedList<DirectNode> stack = new LinkedList<DirectNode>(); + stack.add(dgraph.first); + + Set<DirectNode> setVisited = new HashSet<DirectNode>(); + + while (!stack.isEmpty()) { + + DirectNode node = stack.removeFirst(); + + if (setVisited.contains(node)) { + continue; + } + setVisited.add(node); + + BasicBlockStatement blockStatement = null; + if (node.block != null) { + blockStatement = node.block; + } + else if (node.preds.size() == 1) { + blockStatement = node.preds.get(0).block; + } + + boolean isTrueExit = true; + + if (firstcode != 1) { + + isTrueExit = false; + + for (int i = 0; i < node.exprents.size(); i++) { + Exprent exprent = node.exprents.get(i); + + if (firstcode == 0) { + List<Exprent> lst = exprent.getAllExprents(); + lst.add(exprent); + + boolean found = false; + for (Exprent expr : lst) { + if (expr.type == Exprent.EXPRENT_VAR && new VarVersionPaar((VarExprent)expr).equals(varpaar)) { + found = true; + break; + } + } + + if (found) { + found = false; + if (exprent.type == Exprent.EXPRENT_EXIT) { + ExitExprent exexpr = (ExitExprent)exprent; + if (exexpr.getExittype() == ExitExprent.EXIT_THROW && exexpr.getValue().type == Exprent.EXPRENT_VAR) { + found = true; + } + } + + if (!found) { + return null; + } + else { + isTrueExit = true; + } + } + } + else if (firstcode == 2) { + // search for a load instruction + if (exprent.type == Exprent.EXPRENT_ASSIGNMENT) { + AssignmentExprent assexpr = (AssignmentExprent)exprent; + if (assexpr.getRight().type == Exprent.EXPRENT_VAR && + new VarVersionPaar((VarExprent)assexpr.getRight()).equals(varpaar)) { + + Exprent next = null; + if (i == node.exprents.size() - 1) { + if (node.succs.size() == 1) { + DirectNode nd = node.succs.get(0); + if (!nd.exprents.isEmpty()) { + next = nd.exprents.get(0); + } + } + } + else { + next = node.exprents.get(i + 1); + } + + boolean found = false; + if (next != null && next.type == Exprent.EXPRENT_EXIT) { + ExitExprent exexpr = (ExitExprent)next; + if (exexpr.getExittype() == ExitExprent.EXIT_THROW && exexpr.getValue().type == Exprent.EXPRENT_VAR + && assexpr.getLeft().equals(exexpr.getValue())) { + found = true; + } + } + + if (!found) { + return null; + } + else { + isTrueExit = true; + } + } + } + } + } + } + + // find finally exits + if (blockStatement != null && blockStatement.getBlock() != null) { + Statement handler = fstat.getHandler(); + for (StatEdge edge : blockStatement.getSuccessorEdges(Statement.STATEDGE_DIRECT_ALL)) { + if (edge.getType() != StatEdge.TYPE_REGULAR && handler.containsStatement(blockStatement) + && !handler.containsStatement(edge.getDestination())) { + Boolean existingFlag = mapLast.get(blockStatement.getBlock()); + // note: the dummy node is also processed! + if (existingFlag == null || !existingFlag) { + mapLast.put(blockStatement.getBlock(), isTrueExit); + break; + } + } + } + } + + stack.addAll(node.succs); + } + + // empty finally block? + if (fstat.getHandler().type == Statement.TYPE_BASICBLOCK) { + + boolean isEmpty = false; + boolean isFirstLast = mapLast.containsKey(firstBasicBlock); + InstructionSequence seq = firstBasicBlock.getSeq(); + + switch (firstcode) { + case 0: + isEmpty = isFirstLast && seq.length() == 1; + break; + case 1: + isEmpty = seq.length() == 1; + break; + case 2: + isEmpty = isFirstLast ? seq.length() == 3 : seq.length() == 1; + } + + if (isEmpty) { + firstcode = 3; + } + } + + return new Record(firstcode, mapLast); + } + + private static void insertSemaphore(ControlFlowGraph graph, + Set<BasicBlock> setTry, + BasicBlock head, + BasicBlock handler, + int var, + Record information, + int bytecode_version) { + + Set<BasicBlock> setCopy = new HashSet<BasicBlock>(setTry); + + int finallytype = information.firstCode; + Map<BasicBlock, Boolean> mapLast = information.mapLast; + + // first and last statements + removeExceptionInstructionsEx(handler, 1, finallytype); + for (Entry<BasicBlock, Boolean> entry : mapLast.entrySet()) { + BasicBlock last = entry.getKey(); + + if (entry.getValue()) { + removeExceptionInstructionsEx(last, 2, finallytype); + graph.getFinallyExits().add(last); + } + } + + // disable semaphore at statement exit points + for (BasicBlock block : setTry) { + + List<BasicBlock> lstSucc = block.getSuccs(); + for (BasicBlock dest : lstSucc) { + + // break out + if (!setCopy.contains(dest) && dest != graph.getLast()) { + // disable semaphore + SimpleInstructionSequence seq = new SimpleInstructionSequence(); + + seq.addInstruction(ConstantsUtil + .getInstructionInstance(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, + new int[]{0}), -1); + seq.addInstruction(ConstantsUtil + .getInstructionInstance(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, + new int[]{var}), -1); + + // build a separate block + BasicBlock newblock = new BasicBlock(++graph.last_id); + newblock.setSeq(seq); + + // insert between block and dest + block.replaceSuccessor(dest, newblock); + newblock.addSuccessor(dest); + setCopy.add(newblock); + graph.getBlocks().addWithKey(newblock, newblock.id); + + // exception ranges + // FIXME: special case synchronized + + // copy exception edges and extend protected ranges + for (int j = 0; j < block.getSuccExceptions().size(); j++) { + BasicBlock hd = block.getSuccExceptions().get(j); + newblock.addSuccessorException(hd); + + ExceptionRangeCFG range = graph.getExceptionRange(hd, block); + range.getProtectedRange().add(newblock); + } + } + } + } + + // enable semaphor at the statement entrance + SimpleInstructionSequence seq = new SimpleInstructionSequence(); + seq.addInstruction( + ConstantsUtil.getInstructionInstance(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{1}), + -1); + seq.addInstruction( + ConstantsUtil.getInstructionInstance(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}), + -1); + + BasicBlock newhead = new BasicBlock(++graph.last_id); + newhead.setSeq(seq); + + insertBlockBefore(graph, head, newhead); + + // initialize semaphor with false + seq = new SimpleInstructionSequence(); + seq.addInstruction( + ConstantsUtil.getInstructionInstance(CodeConstants.opc_bipush, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{0}), + -1); + seq.addInstruction( + ConstantsUtil.getInstructionInstance(CodeConstants.opc_istore, false, CodeConstants.GROUP_GENERAL, bytecode_version, new int[]{var}), + -1); + + BasicBlock newheadinit = new BasicBlock(++graph.last_id); + newheadinit.setSeq(seq); + + insertBlockBefore(graph, newhead, newheadinit); + + setCopy.add(newhead); + setCopy.add(newheadinit); + + for (BasicBlock hd : new HashSet<BasicBlock>(newheadinit.getSuccExceptions())) { + ExceptionRangeCFG range = graph.getExceptionRange(hd, newheadinit); + + if (setCopy.containsAll(range.getProtectedRange())) { + newheadinit.removeSuccessorException(hd); + range.getProtectedRange().remove(newheadinit); + } + } + } + + + private static void insertBlockBefore(ControlFlowGraph graph, BasicBlock oldblock, BasicBlock newblock) { + + List<BasicBlock> lstTemp = new ArrayList<BasicBlock>(); + lstTemp.addAll(oldblock.getPreds()); + lstTemp.addAll(oldblock.getPredExceptions()); + + // replace predecessors + for (BasicBlock pred : lstTemp) { + pred.replaceSuccessor(oldblock, newblock); + } + + // copy exception edges and extend protected ranges + for (BasicBlock hd : oldblock.getSuccExceptions()) { + newblock.addSuccessorException(hd); + + ExceptionRangeCFG range = graph.getExceptionRange(hd, oldblock); + range.getProtectedRange().add(newblock); + } + + // replace handler + for (ExceptionRangeCFG range : graph.getExceptions()) { + if (range.getHandler() == oldblock) { + range.setHandler(newblock); + } + } + + newblock.addSuccessor(oldblock); + graph.getBlocks().addWithKey(newblock, newblock.id); + if (graph.getFirst() == oldblock) { + graph.setFirst(newblock); + } + } + + private static HashSet<BasicBlock> getAllBasicBlocks(Statement stat) { + + List<Statement> lst = new LinkedList<Statement>(); + lst.add(stat); + + int index = 0; + do { + Statement st = lst.get(index); + + if (st.type == Statement.TYPE_BASICBLOCK) { + index++; + } + else { + lst.addAll(st.getStats()); + lst.remove(index); + } + } + while (index < lst.size()); + + HashSet<BasicBlock> res = new HashSet<BasicBlock>(); + + for (Statement st : lst) { + res.add(((BasicBlockStatement)st).getBlock()); + } + + return res; + } + + + private boolean verifyFinallyEx(ControlFlowGraph graph, CatchAllStatement fstat, Record information) { + + HashSet<BasicBlock> tryBlocks = getAllBasicBlocks(fstat.getFirst()); + HashSet<BasicBlock> catchBlocks = getAllBasicBlocks(fstat.getHandler()); + + int finallytype = information.firstCode; + Map<BasicBlock, Boolean> mapLast = information.mapLast; + + BasicBlock first = fstat.getHandler().getBasichead().getBlock(); + boolean skippedFirst = false; + + if (finallytype == 3) { + // empty finally + removeExceptionInstructionsEx(first, 3, finallytype); + + if (mapLast.containsKey(first)) { + graph.getFinallyExits().add(first); + } + + return true; + } + else { + if (first.getSeq().length() == 1 && finallytype > 0) { + BasicBlock firstsuc = first.getSuccs().get(0); + if (catchBlocks.contains(firstsuc)) { + first = firstsuc; + skippedFirst = true; + } + } + } + + // identify start blocks + HashSet<BasicBlock> startBlocks = new HashSet<BasicBlock>(); + for (BasicBlock block : tryBlocks) { + startBlocks.addAll(block.getSuccs()); + } + // throw in the try body will point directly to the dummy exit + // so remove dummy exit + startBlocks.remove(graph.getLast()); + startBlocks.removeAll(tryBlocks); + + List<Area> lstAreas = new ArrayList<Area>(); + + for (BasicBlock start : startBlocks) { + + Area arr = compareSubgraphsEx(graph, start, catchBlocks, first, finallytype, mapLast, skippedFirst); + if (arr == null) { + return false; + } + + lstAreas.add(arr); + } + + // try { + // DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true); + // } catch(Exception ex){ex.printStackTrace();} + + // delete areas + for (Area area : lstAreas) { + deleteArea(graph, area); + } + + // try { + // DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true); + // } catch(Exception ex){ex.printStackTrace();} + + // INFO: empty basic blocks may remain in the graph! + for (Entry<BasicBlock, Boolean> entry : mapLast.entrySet()) { + BasicBlock last = entry.getKey(); + + if (entry.getValue()) { + removeExceptionInstructionsEx(last, 2, finallytype); + graph.getFinallyExits().add(last); + } + } + + removeExceptionInstructionsEx(fstat.getHandler().getBasichead().getBlock(), 1, finallytype); + + return true; + } + + private static class Area { + private final BasicBlock start; + private final Set<BasicBlock> sample; + private final BasicBlock next; + + private Area(BasicBlock start, Set<BasicBlock> sample, BasicBlock next) { + this.start = start; + this.sample = sample; + this.next = next; + } + } + + private Area compareSubgraphsEx(ControlFlowGraph graph, + BasicBlock startSample, + HashSet<BasicBlock> catchBlocks, + BasicBlock startCatch, + int finallytype, + Map<BasicBlock, Boolean> mapLast, + boolean skippedFirst) { + + class BlockStackEntry { + public BasicBlock blockCatch; + public BasicBlock blockSample; + + // TODO: correct handling (merging) of multiple paths + public List<int[]> lstStoreVars; + + public BlockStackEntry(BasicBlock blockCatch, BasicBlock blockSample, List<int[]> lstStoreVars) { + this.blockCatch = blockCatch; + this.blockSample = blockSample; + this.lstStoreVars = new ArrayList<int[]>(lstStoreVars); + } + } + + List<BlockStackEntry> stack = new LinkedList<BlockStackEntry>(); + + Set<BasicBlock> setSample = new HashSet<BasicBlock>(); + + Map<String, BasicBlock[]> mapNext = new HashMap<String, BasicBlock[]>(); + + stack.add(new BlockStackEntry(startCatch, startSample, new ArrayList<int[]>())); + + while (!stack.isEmpty()) { + + BlockStackEntry entry = stack.remove(0); + BasicBlock blockCatch = entry.blockCatch; + BasicBlock blockSample = entry.blockSample; + + boolean isFirstBlock = !skippedFirst && blockCatch == startCatch; + boolean isLastBlock = mapLast.containsKey(blockCatch); + boolean isTrueLastBlock = isLastBlock && mapLast.get(blockCatch); + + if (!compareBasicBlocksEx(graph, blockCatch, blockSample, (isFirstBlock ? 1 : 0) | (isTrueLastBlock ? 2 : 0), finallytype, + entry.lstStoreVars)) { + return null; + } + + if (blockSample.getSuccs().size() != blockCatch.getSuccs().size()) { + return null; + } + + setSample.add(blockSample); + + // direct successors + for (int i = 0; i < blockCatch.getSuccs().size(); i++) { + BasicBlock sucCatch = blockCatch.getSuccs().get(i); + BasicBlock sucSample = blockSample.getSuccs().get(i); + + if (catchBlocks.contains(sucCatch) && !setSample.contains(sucSample)) { + stack.add(new BlockStackEntry(sucCatch, sucSample, entry.lstStoreVars)); + } + } + + + // exception successors + if (isLastBlock && blockSample.getSeq().isEmpty()) { + // do nothing, blockSample will be removed anyway + } + else { + if (blockCatch.getSuccExceptions().size() == blockSample.getSuccExceptions().size()) { + for (int i = 0; i < blockCatch.getSuccExceptions().size(); i++) { + BasicBlock sucCatch = blockCatch.getSuccExceptions().get(i); + BasicBlock sucSample = blockSample.getSuccExceptions().get(i); + + String excCatch = graph.getExceptionRange(sucCatch, blockCatch).getUniqueExceptionsString(); + String excSample = graph.getExceptionRange(sucSample, blockSample).getUniqueExceptionsString(); + + // FIXME: compare handlers if possible + boolean equalexc = excCatch == null ? excSample == null : excCatch.equals(excSample); + + if (equalexc) { + if (catchBlocks.contains(sucCatch) && !setSample.contains(sucSample)) { + + List<int[]> lst = entry.lstStoreVars; + + if (sucCatch.getSeq().length() > 0 && sucSample.getSeq().length() > 0) { + Instruction instrCatch = sucCatch.getSeq().getInstr(0); + Instruction instrSample = sucSample.getSeq().getInstr(0); + + if (instrCatch.opcode == CodeConstants.opc_astore && + instrSample.opcode == CodeConstants.opc_astore) { + lst = new ArrayList<int[]>(lst); + lst.add(new int[]{instrCatch.getOperand(0), instrSample.getOperand(0)}); + } + } + + stack.add(new BlockStackEntry(sucCatch, sucSample, lst)); + } + } + else { + return null; + } + } + } + else { + return null; + } + } + + if (isLastBlock) { + Set<BasicBlock> setSuccs = new HashSet<BasicBlock>(blockSample.getSuccs()); + setSuccs.removeAll(setSample); + + for (BlockStackEntry stackent : stack) { + setSuccs.remove(stackent.blockSample); + } + + for (BasicBlock succ : setSuccs) { + if (graph.getLast() != succ) { // FIXME: why? + mapNext.put(blockSample.id + "#" + succ.id, new BasicBlock[]{blockSample, succ, isTrueLastBlock ? succ : null}); + } + } + } + } + + return new Area(startSample, setSample, getUniqueNext(graph, new HashSet<BasicBlock[]>(mapNext.values()))); + } + + private static BasicBlock getUniqueNext(ControlFlowGraph graph, Set<BasicBlock[]> setNext) { + + // precondition: there is at most one true exit path in a finally statement + + BasicBlock next = null; + boolean multiple = false; + + for (BasicBlock[] arr : setNext) { + + if (arr[2] != null) { + next = arr[1]; + multiple = false; + break; + } + else { + if (next == null) { + next = arr[1]; + } + else if (next != arr[1]) { + multiple = true; + } + + if (arr[1].getPreds().size() == 1) { + next = arr[1]; + } + } + } + + if (multiple) { // TODO: generic solution + for (BasicBlock[] arr : setNext) { + BasicBlock block = arr[1]; + + if (block != next) { + if (InterpreterUtil.equalSets(next.getSuccs(), block.getSuccs())) { + InstructionSequence seqNext = next.getSeq(); + InstructionSequence seqBlock = block.getSeq(); + + if (seqNext.length() == seqBlock.length()) { + for (int i = 0; i < seqNext.length(); i++) { + Instruction instrNext = seqNext.getInstr(i); + Instruction instrBlock = seqBlock.getInstr(i); + + if (instrNext.opcode != instrBlock.opcode || instrNext.wide != instrBlock.wide + || instrNext.operandsCount() != instrBlock.operandsCount()) { + return null; + } + + for (int j = 0; j < instrNext.getOperands().length; j++) { + if (instrNext.getOperand(j) != instrBlock.getOperand(j)) { + return null; + } + } + } + } + else { + return null; + } + } + else { + return null; + } + } + } + + // try { + // DotExporter.toDotFile(graph, new File("c:\\Temp\\fern5.dot"), true); + // } catch(IOException ex) { + // ex.printStackTrace(); + // } + + for (BasicBlock[] arr : setNext) { + if (arr[1] != next) { + // FIXME: exception edge possible? + arr[0].removeSuccessor(arr[1]); + arr[0].addSuccessor(next); + } + } + + DeadCodeHelper.removeDeadBlocks(graph); + } + + return next; + } + + private boolean compareBasicBlocksEx(ControlFlowGraph graph, + BasicBlock pattern, + BasicBlock sample, + int type, + int finallytype, + List<int[]> lstStoreVars) { + + InstructionSequence seqPattern = pattern.getSeq(); + InstructionSequence seqSample = sample.getSeq(); + + if (type != 0) { + seqPattern = seqPattern.clone(); + + if ((type & 1) > 0) { // first + if (finallytype > 0) { + seqPattern.removeInstruction(0); + } + } + + if ((type & 2) > 0) { // last + if (finallytype == 0 || finallytype == 2) { + seqPattern.removeInstruction(seqPattern.length() - 1); + } + + if (finallytype == 2) { + seqPattern.removeInstruction(seqPattern.length() - 1); + } + } + } + + if (seqPattern.length() > seqSample.length()) { + return false; + } + + for (int i = 0; i < seqPattern.length(); i++) { + Instruction instrPattern = seqPattern.getInstr(i); + Instruction instrSample = seqSample.getInstr(i); + + // compare instructions with respect to jumps + if (!equalInstructions(instrPattern, instrSample, lstStoreVars)) { + return false; + } + } + + if (seqPattern.length() < seqSample.length()) { // split in two blocks + + SimpleInstructionSequence seq = new SimpleInstructionSequence(); + for (int i = seqSample.length() - 1; i >= seqPattern.length(); i--) { + seq.addInstruction(0, seqSample.getInstr(i), -1); + seqSample.removeInstruction(i); + } + + BasicBlock newblock = new BasicBlock(++graph.last_id); + newblock.setSeq(seq); + + List<BasicBlock> lstTemp = new ArrayList<BasicBlock>(); + lstTemp.addAll(sample.getSuccs()); + + // move successors + for (BasicBlock suc : lstTemp) { + sample.removeSuccessor(suc); + newblock.addSuccessor(suc); + } + + sample.addSuccessor(newblock); + + graph.getBlocks().addWithKey(newblock, newblock.id); + + Set<BasicBlock> setFinallyExits = graph.getFinallyExits(); + if (setFinallyExits.contains(sample)) { + setFinallyExits.remove(sample); + setFinallyExits.add(newblock); + } + + // copy exception edges and extend protected ranges + for (int j = 0; j < sample.getSuccExceptions().size(); j++) { + BasicBlock hd = sample.getSuccExceptions().get(j); + newblock.addSuccessorException(hd); + + ExceptionRangeCFG range = graph.getExceptionRange(hd, sample); + range.getProtectedRange().add(newblock); + } + } + + return true; + } + + public boolean equalInstructions(Instruction first, Instruction second, List<int[]> lstStoreVars) { + if (first.opcode != second.opcode || first.wide != second.wide + || first.operandsCount() != second.operandsCount()) { + return false; + } + + if (first.group != CodeConstants.GROUP_JUMP && first.getOperands() != null) { // FIXME: switch comparison + for (int i = 0; i < first.getOperands().length; i++) { + + int firstOp = first.getOperand(i); + int secondOp = second.getOperand(i); + + if (firstOp != secondOp) { + + // a-load/store instructions + if (first.opcode == CodeConstants.opc_aload || first.opcode == CodeConstants.opc_astore) { + for (int[] arr : lstStoreVars) { + if (arr[0] == firstOp && arr[1] == secondOp) { + return true; + } + } + } + + return false; + } + } + } + + return true; + } + + private static void deleteArea(ControlFlowGraph graph, Area area) { + + BasicBlock start = area.start; + BasicBlock next = area.next; + + if (start == next) { + return; + } + + if (next == null) { + // dummy exit block + next = graph.getLast(); + } + + // collect common exception ranges of predecessors and successors + Set<BasicBlock> setCommonExceptionHandlers = new HashSet<BasicBlock>(next.getSuccExceptions()); + for (BasicBlock pred : start.getPreds()) { + setCommonExceptionHandlers.retainAll(pred.getSuccExceptions()); + } + + boolean is_outside_range = false; + + Set<BasicBlock> setPredecessors = new HashSet<BasicBlock>(start.getPreds()); + + // replace start with next + for (BasicBlock pred : setPredecessors) { + pred.replaceSuccessor(start, next); + } + + Set<BasicBlock> setBlocks = area.sample; + + Set<ExceptionRangeCFG> setCommonRemovedExceptionRanges = null; + + // remove all the blocks inbetween + for (BasicBlock block : setBlocks) { + + // artificial basic blocks (those resulted from splitting) + // can belong to more than one area + if (graph.getBlocks().containsKey(block.id)) { + + if (!block.getSuccExceptions().containsAll(setCommonExceptionHandlers)) { + is_outside_range = true; + } + + Set<ExceptionRangeCFG> setRemovedExceptionRanges = new HashSet<ExceptionRangeCFG>(); + for (BasicBlock handler : block.getSuccExceptions()) { + setRemovedExceptionRanges.add(graph.getExceptionRange(handler, block)); + } + + if (setCommonRemovedExceptionRanges == null) { + setCommonRemovedExceptionRanges = setRemovedExceptionRanges; + } + else { + setCommonRemovedExceptionRanges.retainAll(setRemovedExceptionRanges); + } + + // shift extern edges on splitted blocks + if (block.getSeq().isEmpty() && block.getSuccs().size() == 1) { + BasicBlock succs = block.getSuccs().get(0); + for (BasicBlock pred : new ArrayList<BasicBlock>(block.getPreds())) { + if (!setBlocks.contains(pred)) { + pred.replaceSuccessor(block, succs); + } + } + + if (graph.getFirst() == block) { + graph.setFirst(succs); + } + } + + graph.removeBlock(block); + } + } + + if (is_outside_range) { + + // new empty block + BasicBlock emptyblock = new BasicBlock(++graph.last_id); + emptyblock.setSeq(new SimpleInstructionSequence()); + graph.getBlocks().addWithKey(emptyblock, emptyblock.id); + + // add to ranges if necessary + if (setCommonRemovedExceptionRanges != null) { + for (ExceptionRangeCFG range : setCommonRemovedExceptionRanges) { + emptyblock.addSuccessorException(range.getHandler()); + range.getProtectedRange().add(emptyblock); + } + } + + // insert between predecessors and next + emptyblock.addSuccessor(next); + for (BasicBlock pred : setPredecessors) { + pred.replaceSuccessor(next, emptyblock); + } + } + } + + private static void removeExceptionInstructionsEx(BasicBlock block, int blocktype, int finallytype) { + + InstructionSequence seq = block.getSeq(); + + if (finallytype == 3) { // empty finally handler + for (int i = seq.length() - 1; i >= 0; i--) { + seq.removeInstruction(i); + } + } + else { + if ((blocktype & 1) > 0) { // first + if (finallytype == 2 || finallytype == 1) { // astore or pop + seq.removeInstruction(0); + } + } + + if ((blocktype & 2) > 0) { // last + if (finallytype == 2 || finallytype == 0) { + seq.removeInstruction(seq.length() - 1); + } + + if (finallytype == 2) { // astore + seq.removeInstruction(seq.length() - 1); + } + } + } + } +} |