java-decompiler: post-import cleanup (classes moved)

1 files changed, 438 insertions, 0 deletions

diff --git a/src/org/jetbrains/java/decompiler/modules/code/DeadCodeHelper.java b/src/org/jetbrains/java/decompiler/modules/code/DeadCodeHelper.java
new file mode 100644
index 0000000..4d39e68
--- /dev/null
+++ b/src/org/jetbrains/java/decompiler/modules/code/DeadCodeHelper.java
@@ -0,0 +1,438 @@
+/*
+ *    Fernflower - The Analytical Java Decompiler
+ *    http://www.reversed-java.com
+ *
+ *    (C) 2008 - 2010, Stiver
+ *
+ *    This software is NEITHER public domain NOR free software 
+ *    as per GNU License. See license.txt for more details.
+ *
+ *    This software is distributed WITHOUT ANY WARRANTY; without 
+ *    even the implied warranty of MERCHANTABILITY or FITNESS FOR 
+ *    A PARTICULAR PURPOSE. 
+ */
+
+package org.jetbrains.java.decompiler.modules.code;
+
+import java.util.ArrayList;
+import java.util.HashSet;
+import java.util.LinkedList;
+import java.util.List;
+
+import org.jetbrains.java.decompiler.code.CodeConstants;
+import org.jetbrains.java.decompiler.code.Instruction;
+import org.jetbrains.java.decompiler.code.InstructionSequence;
+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.extern.IFernflowerPreferences;
+
+public class DeadCodeHelper {
+
+	public static void removeDeadBlocks(ControlFlowGraph graph) {
+		
+		LinkedList<BasicBlock> stack = new LinkedList<BasicBlock>();
+		HashSet<BasicBlock> setStacked = new HashSet<BasicBlock>();
+		
+		stack.add(graph.getFirst());
+		setStacked.add(graph.getFirst());
+
+		while(!stack.isEmpty()) {
+			BasicBlock block = stack.removeFirst();
+		
+			List<BasicBlock> lstSuccs = new ArrayList<BasicBlock>(block.getSuccs());
+			lstSuccs.addAll(block.getSuccExceptions());
+			
+			for(BasicBlock succ : lstSuccs) {
+				if(!setStacked.contains(succ)) {
+					stack.add(succ);
+					setStacked.add(succ);
+				}
+			}
+		}
+		
+		HashSet<BasicBlock> setAllBlocks = new HashSet<BasicBlock>(graph.getBlocks());
+		setAllBlocks.removeAll(setStacked);
+		
+		for(BasicBlock block : setAllBlocks) {
+			graph.removeBlock(block);
+		}
+	}
+	
+	public static void removeEmptyBlocks(ControlFlowGraph graph) {
+
+		List<BasicBlock> blocks = graph.getBlocks(); 
+		
+		boolean cont;
+		do {
+			cont = false;
+			
+			for(int i=blocks.size()-1;i>=0;i--) {
+				BasicBlock block = (BasicBlock)blocks.get(i);
+				
+				if(removeEmptyBlock(graph, block, false)) {
+					cont = true;
+					break;
+				}
+			}
+			
+		} while(cont);
+	}
+	
+	private static boolean removeEmptyBlock(ControlFlowGraph graph, BasicBlock block, boolean merging) {
+		
+		boolean deletedRanges = false;
+		
+		if(block.getSeq().isEmpty()) {
+			
+			if(block.getSuccs().size() > 1) {
+				if(block.getPreds().size()>1) {
+					// ambiguous block
+					throw new RuntimeException("ERROR: empty block with multiple predecessors and successors found"); 
+				} else if(!merging) {
+					throw new RuntimeException("ERROR: empty block with multiple successors found"); 
+				}
+			}
+			
+			HashSet<BasicBlock> setExits = new HashSet<BasicBlock>(graph.getLast().getPreds());
+
+			if(block.getPredExceptions().isEmpty() && 
+					(!setExits.contains(block) || block.getPreds().size() == 1)) {
+				
+				if(setExits.contains(block)) {
+					BasicBlock pred = block.getPreds().get(0);
+					
+					// FIXME: flag in the basic block
+					if(pred.getSuccs().size() != 1 || (!pred.getSeq().isEmpty()
+							&& pred.getSeq().getLastInstr().group == CodeConstants.GROUP_SWITCH)) {
+						return false;
+					}
+				}
+				
+				HashSet<BasicBlock> setPreds = new HashSet<BasicBlock>(block.getPreds());
+				HashSet<BasicBlock> setSuccs = new HashSet<BasicBlock>(block.getSuccs());
+
+				// collect common exception ranges of predecessors and successors
+				HashSet<BasicBlock> setCommonExceptionHandlers = null; 
+				for(int i = 0; i < 2; ++i) {
+					for(BasicBlock pred : i == 0 ? setPreds : setSuccs) {
+						if(setCommonExceptionHandlers == null) {
+							setCommonExceptionHandlers = new HashSet<BasicBlock>(pred.getSuccExceptions());
+						} else {
+							setCommonExceptionHandlers.retainAll(pred.getSuccExceptions());
+						}
+					}
+				}
+
+				// check the block to be in each of the common ranges
+				if(setCommonExceptionHandlers != null && !setCommonExceptionHandlers.isEmpty()) {
+					for(BasicBlock handler : setCommonExceptionHandlers) {
+						if(!block.getSuccExceptions().contains(handler)) {
+							return false;
+						}
+					}
+				}
+				
+				// remove ranges consisting of this one block
+				List<ExceptionRangeCFG> lstRanges = graph.getExceptions();
+				for(int i=lstRanges.size()-1;i>=0;i--) {
+					ExceptionRangeCFG range = lstRanges.get(i);
+					List<BasicBlock> lst = range.getProtectedRange();
+
+					if(lst.size() == 1 && lst.get(0) == block) {
+						if(DecompilerContext.getOption(IFernflowerPreferences.REMOVE_EMPTY_RANGES)) {
+							block.removeSuccessorException(range.getHandler());
+							lstRanges.remove(i);
+							
+							deletedRanges = true;
+						} else {
+							return false;
+						}
+					}
+				}
+
+				
+				// connect remaining nodes
+				if(merging) {
+					BasicBlock pred = block.getPreds().get(0);
+					pred.removeSuccessor(block);
+					
+					List<BasicBlock> lstSuccs = new ArrayList<BasicBlock>(block.getSuccs());
+					for(BasicBlock succ : lstSuccs) {
+						block.removeSuccessor(succ);
+						pred.addSuccessor(succ);
+					}
+					
+				} else {
+					for(BasicBlock pred : setPreds) {
+						for(BasicBlock succ : setSuccs) {
+							pred.replaceSuccessor(block, succ);
+						}
+					}
+				}
+
+				// finally exit edges
+				HashSet<BasicBlock> setFinallyExits = graph.getFinallyExits(); 
+				if(setFinallyExits.contains(block)) {
+					setFinallyExits.remove(block);
+					setFinallyExits.add(setPreds.iterator().next());
+				}
+				
+				// replace first if necessary
+				if(graph.getFirst() == block) {
+					if(setSuccs.size() != 1) {
+						throw new RuntimeException("multiple or no entry blocks!");
+					} else {
+						graph.setFirst(setSuccs.iterator().next());
+					}
+				}
+
+				// remove this block
+				graph.removeBlock(block);
+				
+				if(deletedRanges) {
+					DeadCodeHelper.removeDeadBlocks(graph);
+				}
+			}
+		}
+		
+		return deletedRanges;
+	}
+	
+	
+	public static boolean isDominator(ControlFlowGraph graph, BasicBlock block, BasicBlock dom) {
+		
+		HashSet<BasicBlock> marked = new HashSet<BasicBlock>();
+		
+		if(block == dom) {
+			return true;
+		}
+		
+		LinkedList<BasicBlock> lstNodes = new LinkedList<BasicBlock>();
+		lstNodes.add(block);
+
+		while(!lstNodes.isEmpty()) {
+			
+			BasicBlock node = (BasicBlock)lstNodes.remove(0);
+			if(marked.contains(node)) {
+				continue;
+			} else {
+				marked.add(node);
+			}
+			
+			if(node == graph.getFirst()) {
+				return false;
+			}
+
+			for(int i=0;i<node.getPreds().size();i++) {
+				BasicBlock pred = (BasicBlock)node.getPreds().get(i);
+				if(!marked.contains(pred) && pred != dom) {
+					lstNodes.add(pred);
+				}
+			}
+			
+			for(int i=0;i<node.getPredExceptions().size();i++) {
+				BasicBlock pred = (BasicBlock)node.getPredExceptions().get(i);
+				if(!marked.contains(pred) && pred != dom) {
+					lstNodes.add(pred);
+				}
+			}
+		}
+		
+		return true;
+	}
+	
+	public static void removeGotos(ControlFlowGraph graph) {
+		
+		for(BasicBlock block : graph.getBlocks()) {
+			Instruction instr = block.getLastInstruction();
+			
+			if(instr!=null && instr.opcode == CodeConstants.opc_goto) {
+				block.getSeq().removeInstruction(block.getSeq().length()-1);
+			}
+		}
+
+		DeadCodeHelper.removeEmptyBlocks(graph);
+	}
+	
+	public static void connectDummyExitBlock(ControlFlowGraph graph) {
+		
+		BasicBlock exit = graph.getLast();
+		for(BasicBlock block : new HashSet<BasicBlock>(exit.getPreds())) {
+			exit.removePredecessor(block);
+			block.addSuccessor(exit);
+		}
+	}
+	
+	public static void incorporateValueReturns(ControlFlowGraph graph) {
+
+		for(BasicBlock block: graph.getBlocks()) {
+			InstructionSequence seq = block.getSeq();
+			
+			int len = seq.length();
+			if(len > 0 && len < 3) {
+				
+				boolean ok = false;
+				
+				if(seq.getLastInstr().opcode >= CodeConstants.opc_ireturn && seq.getLastInstr().opcode <= CodeConstants.opc_return) {
+					if(len == 1) {
+						ok = true;
+					} else if(seq.getLastInstr().opcode != CodeConstants.opc_return){
+						switch(seq.getInstr(0).opcode) {
+						case CodeConstants.opc_iload:		
+						case CodeConstants.opc_lload:		
+						case CodeConstants.opc_fload:		
+						case CodeConstants.opc_dload:		
+						case CodeConstants.opc_aload:		
+						case CodeConstants.opc_aconst_null:
+						case CodeConstants.opc_bipush:
+						case CodeConstants.opc_sipush:
+						case CodeConstants.opc_lconst_0:
+						case CodeConstants.opc_lconst_1:
+						case CodeConstants.opc_fconst_0:    
+						case CodeConstants.opc_fconst_1:    
+						case CodeConstants.opc_fconst_2:
+						case CodeConstants.opc_dconst_0:    
+						case CodeConstants.opc_dconst_1:
+						case CodeConstants.opc_ldc:		
+						case CodeConstants.opc_ldc_w:
+						case CodeConstants.opc_ldc2_w:
+							ok = true;
+						}
+					}
+				}
+				
+				if(ok) {
+					
+					if(!block.getPreds().isEmpty()) {
+						
+						HashSet<BasicBlock> setPredHandlersUnion = new HashSet<BasicBlock>(); 
+						HashSet<BasicBlock> setPredHandlersIntersection = new HashSet<BasicBlock>(); 
+						
+						boolean firstpred = true;
+						for(BasicBlock pred : block.getPreds()) {
+							if(firstpred) {
+								setPredHandlersIntersection.addAll(pred.getSuccExceptions());
+								firstpred = false;
+							} else {
+								setPredHandlersIntersection.retainAll(pred.getSuccExceptions());
+							}
+
+							setPredHandlersUnion.addAll(pred.getSuccExceptions());
+						}
+						
+						// add exception ranges from predecessors
+						setPredHandlersIntersection.removeAll(block.getSuccExceptions());
+						BasicBlock predecessor = block.getPreds().get(0);
+						
+						for(BasicBlock handler : setPredHandlersIntersection) {
+							ExceptionRangeCFG range = graph.getExceptionRange(handler, predecessor);
+
+							range.getProtectedRange().add(block);
+							block.addSuccessorException(handler);
+						}
+
+						// remove redundant ranges
+						HashSet<BasicBlock> setRangesToBeRemoved = new HashSet<BasicBlock>(block.getSuccExceptions());
+						setRangesToBeRemoved.removeAll(setPredHandlersUnion);
+						
+						for(BasicBlock handler : setRangesToBeRemoved) {
+							ExceptionRangeCFG range = graph.getExceptionRange(handler, block);
+
+							if(range.getProtectedRange().size() > 1) {
+								range.getProtectedRange().remove(block);
+								block.removeSuccessorException(handler);
+							}
+						}
+					}
+					
+					
+					if(block.getPreds().size() == 1 && block.getPredExceptions().isEmpty()) {
+						
+						BasicBlock bpred = block.getPreds().get(0);
+						if(bpred.getSuccs().size() == 1) {
+							
+							// add exception ranges of predecessor
+							for(BasicBlock succ : bpred.getSuccExceptions()) {
+								if(!block.getSuccExceptions().contains(succ)) {
+									ExceptionRangeCFG range = graph.getExceptionRange(succ, bpred);
+									
+									range.getProtectedRange().add(block);
+									block.addSuccessorException(succ);
+								}
+							}
+
+							// remove superfluous ranges from successors
+							for(BasicBlock succ : new HashSet<BasicBlock>(block.getSuccExceptions())) {
+								if(!bpred.getSuccExceptions().contains(succ)) {
+									ExceptionRangeCFG range = graph.getExceptionRange(succ, block);
+									
+									if(range.getProtectedRange().size() > 1) {
+										range.getProtectedRange().remove(block);
+										block.removeSuccessorException(succ);
+									}
+								}
+							}
+						}
+					}
+					
+				}
+			}
+			
+		}
+		
+	}
+	
+	
+	public static void mergeBasicBlocks(ControlFlowGraph graph) {
+		
+		for(;;) {
+			
+			boolean merged = false;
+			
+			for(BasicBlock block: graph.getBlocks()) {
+	
+				InstructionSequence seq = block.getSeq();
+				
+				if(block.getSuccs().size() == 1) {
+					BasicBlock next = block.getSuccs().get(0);
+
+					if(next != graph.getLast() && (seq.isEmpty() || seq.getLastInstr().group != CodeConstants.GROUP_SWITCH)) {
+						
+						if(next.getPreds().size() == 1 && next.getPredExceptions().isEmpty()
+								&& next != graph.getFirst()) {
+							// TODO: implement a dummy start block
+							boolean sameRanges = true; 
+							for(ExceptionRangeCFG range : graph.getExceptions()) {
+								if(range.getProtectedRange().contains(block) ^
+										range.getProtectedRange().contains(next)) {
+									sameRanges = false;
+									break;
+								}
+							}
+							
+							if(sameRanges) {
+								seq.addSequence(next.getSeq());
+								next.getSeq().clear();
+								
+								removeEmptyBlock(graph, next, true);
+								
+								merged = true;
+								break;
+							}
+						}
+					}
+				}
+				
+			}
+			
+			if(!merged) {
+				break;
+			}
+		}
+		
+	}
+	
+	
+}