localoptimizer.java

Java Optimize and Decompile Environment 源代码

/* LocalOptimizer Copyright (C) 1999-2002 Jochen Hoenicke.
 *
 * This program is free software; you can redistribute it and/or modify
 * it under the terms of the GNU General Public License as published by
 * the Free Software Foundation; either version 2, or (at your option)
 * any later version.
 *
 * This program is distributed in the hope that it will be useful,
 * but WITHOUT ANY WARRANTY; without even the implied warranty of
 * MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE.  See the
 * GNU General Public License for more details.
 *
 * You should have received a copy of the GNU General Public License
 * along with this program; see the file COPYING.  If not, write to
 * the Free Software Foundation, 675 Mass Ave, Cambridge, MA 02139, USA.
 *
 * $Id: LocalOptimizer.java.in,v 1.1.2.2 2002/05/28 17:34:17 hoenicke Exp $
 */

package jode.obfuscator.modules;
import java.util.*;
import jode.bytecode.*;
import jode.obfuscator.*;
import jode.AssertError;
import jode.GlobalOptions;

import java.util.Iterator;
import java.util.ListIterator;

/**
 * This class takes some bytecode and tries to minimize the number
 * of locals used.  It will also remove unnecessary stores.  
 *
 * This class can only work on verified code.  There should also be no
 * deadcode, since the verifier doesn't check that deadcode behaves
 * okay.  
 *
 * This is done in two phases.  First we determine which locals are
 * the same, and which locals have a overlapping life time. In the
 * second phase we will then redistribute the locals with a coloring
 * graph algorithm.
 *
 * The idea for the first phase is: For each read we follow the
 * instruction flow backward to find the corresponding writes.  We can
 * also merge with another control flow that has a different read, in
 * this case we merge with that read, too.
 *
 * The tricky part is the subroutine handling.  We follow the local
 * that is used in a ret and find the corresponding jsr target (there
 * must be only one, if the verifier should accept this class).  While
 * we do this we remember in the info of the ret, which locals are
 * used in that subroutine.
 *
 * When we know the jsr target<->ret correlation, we promote from the
 * nextByAddr of every jsr the locals that are accessed by the
 * subroutine to the corresponding ret and the others to the jsr.  Also
 * we will promote all reads from the jsr targets to the jsr.
 *
 * If you think this might be to complicated, keep in mind that jsr's
 * are not only left by the ret instructions, but also "spontanously"
 * (by not reading the return address again).
 */
public class LocalOptimizer implements Opcodes, CodeTransformer {

    /**
     * This class keeps track of which locals must be the same, which
     * name and type each local (if there is a local variable table) and
     * which other locals have an intersecting life time.
     */
    class LocalInfo {
	LocalInfo shadow = null;

	public LocalInfo getReal() {
	    LocalInfo real = this;
	    while (real.shadow != null)
		real = real.shadow;
	    return real;
	}

	String name;
	String type;
	Vector usingInstrs = new Vector();
	Vector conflictingLocals = new Vector();
	int size;
	int newSlot = -1;

	LocalInfo() {
	}
	
	LocalInfo(InstrInfo instr) {
	    usingInstrs.addElement(instr);
	}

	void conflictsWith(LocalInfo l) {
	    if (shadow != null) {
		getReal().conflictsWith(l);
	    } else {
		l = l.getReal();
		if (!conflictingLocals.contains(l)) {
		    conflictingLocals.addElement(l);
		    l.conflictingLocals.addElement(this);
		}
	    }
	}
	
	void combineInto(LocalInfo l) {
	    if (shadow != null) {
		getReal().combineInto(l);
		return;
	    }
	    l = l.getReal();
	    if (this == l)
		return;
	    shadow = l;
	    if (shadow.name == null) {
		shadow.name = name;
		shadow.type = type;
	    }
	    Enumeration enum = usingInstrs.elements();
	    while (enum.hasMoreElements()) {
		InstrInfo instr = (InstrInfo) enum.nextElement();
		instr.local = l;
		l.usingInstrs.addElement(instr);
	    }
	}

	public int getFirstAddr() {
	    int minAddr = Integer.MAX_VALUE;
	    Enumeration enum = usingInstrs.elements();
	    while (enum.hasMoreElements()) {
		InstrInfo info = (InstrInfo) enum.nextElement();
		if (info.instr.getAddr() < minAddr)
		    minAddr = info.instr.getAddr();
	    }
	    return minAddr;
	}
    }

    private static class TodoQueue {
	public final InstrInfo LAST = new InstrInfo();
	InstrInfo first = LAST;

	public void add(InstrInfo info) {
	    if (info.nextTodo == null) {
		/* only enqueue if not already on queue */
		info.nextTodo = first;
		first = info;
	    }
	}

	public boolean isEmpty() {
	    return first == LAST;
	}

	public InstrInfo remove() {
	    if (first == LAST)
		throw new NoSuchElementException();
	    InstrInfo result = first;
	    first = result.nextTodo;
	    result.nextTodo = null;
	    return result;
	}
    }
    

    /**
     * This class contains information for each instruction.
     */
    static class InstrInfo {
	/**
	 * The next changed InstrInfo, or null, if this instr info did
	 * not changed.
	 */
	InstrInfo nextTodo;

	/**
	 * The LocalInfo that this instruction manipulates, or null
	 * if this is not an ret, iinc, load or store instruction.
	 */
	LocalInfo local;
	/**
	 * For each slot, this contains the InstrInfo of one of the
	 * next Instruction, that may read from that slot, without
	 * prior writing.  */
	InstrInfo[] nextReads;

	/**
	 * This only has a value for ret instructions.  In that case
	 * this bitset contains all locals, that may be used between
	 * jsr and ret.  
	 */
	BitSet usedBySub;
	/**
	 * For each slot if get() is true, no instruction may read
	 * this slot, since it may contain different locals, depending
	 * on flow.  
	 */
	LocalInfo[] lifeLocals;
	/**
	 * If instruction is the destination of a jsr, this contains
	 * the single allowed ret instruction info, or null if there
	 * is no ret at all (or not yet detected).  
	 */
	InstrInfo retInfo;
	/**
	 * If this instruction is a ret, this contains the single
	 * allowed jsr target to which this ret belongs.  
	 */
	InstrInfo jsrTargetInfo;
	/**
	 * The Instruction of this info
	 */
	Instruction instr;
	/**
	 * The next info in the chain.
	 */
	InstrInfo nextInfo;
    }

    BytecodeInfo bc;

    TodoQueue changedInfos;
    InstrInfo firstInfo;
    Hashtable instrInfos;
    boolean produceLVT;
    int maxlocals;

    LocalInfo[] paramLocals;

    public LocalOptimizer() {
    }


    /**
     * Merges the given vector to a new vector.  Both vectors may
     * be null in which case they are interpreted as empty vectors.
     * The vectors will never changed, but the result may be one
     * of the given vectors.
     */
    Vector merge(Vector v1, Vector v2) {
	if (v1 == null || v1.isEmpty())
	    return v2;
	if (v2 == null || v2.isEmpty())
	    return v1;
	Vector result = (Vector) v1.clone();
	Enumeration enum = v2.elements();
	while (enum.hasMoreElements()) {
	    Object elem = enum.nextElement();
	    if (!result.contains(elem))
		result.addElement(elem);
	}
	return result;
    }

    void promoteReads(InstrInfo info, Instruction preInstr,
		      BitSet mergeSet, boolean inverted) {
	InstrInfo preInfo = (InstrInfo) instrInfos.get(preInstr);
	int omitLocal = -1;
	if (preInstr.getOpcode() >= opc_istore
	    && preInstr.getOpcode() <= opc_astore) {
	    /* This is a store */
	    omitLocal = preInstr.getLocalSlot();
	    if (info.nextReads[omitLocal] != null)
		preInfo.local.combineInto(info.nextReads[omitLocal].local);
	}
	for (int i=0; i < maxlocals; i++) {
	    if (info.nextReads[i] != null && i != omitLocal
		&& (mergeSet == null || mergeSet.get(i) != inverted)) {

		if (preInfo.nextReads[i] == null) {
		    preInfo.nextReads[i] = info.nextReads[i];
		    changedInfos.add(preInfo);
		} else {
		    preInfo.nextReads[i].local
			.combineInto(info.nextReads[i].local);
		}
	    }
	}
    }

    void promoteReads(InstrInfo info, Instruction preInstr) {
	promoteReads(info, preInstr, null, false);
    }

    public LocalVariableInfo findLVTEntry(LocalVariableInfo[] lvt, 
					  int slot, int addr) {
	LocalVariableInfo match = null;
	for (int i=0; i < lvt.length; i++) {
	    if (lvt[i].slot == slot
		&& lvt[i].start.getAddr() <= addr
		&& lvt[i].end.getAddr() >= addr) {
		if (match != null
		    && (!match.name.equals(lvt[i].name)
			|| !match.type.equals(lvt[i].type))) {
		    /* Multiple matches..., give no info */
		    return null;
		}
		match = lvt[i];
	    }
	}
	return match;
    }

    public LocalVariableInfo findLVTEntry(LocalVariableInfo[] lvt, 
					  Instruction instr) {
	int addr;
	if (instr.getOpcode() >= opc_istore
	    && instr.getOpcode() <= opc_astore)
	    addr = instr.getNextAddr();
	else
	    addr = instr.getAddr();
	return findLVTEntry(lvt, instr.getLocalSlot(), addr);
    }

    public void calcLocalInfo() {
	maxlocals = bc.getMaxLocals();
	Handler[] handlers = bc.getExceptionHandlers();
	LocalVariableInfo[] lvt = bc.getLocalVariableTable();
	if (lvt != null)
	    produceLVT = true;

	/* Initialize paramLocals */
	{
	    String methodType = bc.getMethodInfo().getType();
	    int paramCount = (bc.getMethodInfo().isStatic() ? 0 : 1)
		+ TypeSignature.getArgumentSize(methodType);
	    paramLocals = new LocalInfo[paramCount];
	    int slot = 0;
	    if (!bc.getMethodInfo().isStatic()) {
		LocalInfo local = new LocalInfo();
		if (lvt != null) {
		    LocalVariableInfo lvi = findLVTEntry(lvt, 0, 0);
		    if (lvi != null) {
			local.name = lvi.name;
			local.type = lvi.type;
		    }
		}
		local.size = 1;
		paramLocals[slot++] = local;
	    }
	    int pos = 1;
	    while (pos < methodType.length()
		   && methodType.charAt(pos) != ')') {

		LocalInfo local = new LocalInfo();
		if (lvt != null) {
		    LocalVariableInfo lvi = findLVTEntry(lvt, slot, 0);
		    if (lvi != null) {
			local.name = lvi.name;
		    }
		}

		int start = pos;
		pos = TypeSignature.skipType(methodType, pos);
		local.type = methodType.substring(start, pos);
		local.size = TypeSignature.getTypeSize(local.type);
		paramLocals[slot] = local;
		slot += local.size;
	    }
	}

	/* Initialize the InstrInfos and LocalInfos
	 */
	changedInfos = new TodoQueue();
	instrInfos = new Hashtable();
	{
	    InstrInfo info = firstInfo = new InstrInfo();
	    Iterator i = bc.getInstructions().iterator();
	    while (true) {
		Instruction instr = (Instruction) i.next();
		instrInfos.put(instr, info);
		info.instr = instr;
		info.nextReads = new InstrInfo[maxlocals];
		if (instr.hasLocalSlot()) {
		    info.local = new LocalInfo(info);
		    if (lvt != null) {
			LocalVariableInfo lvi = findLVTEntry(lvt, instr);
			if (lvi != null) {
			    info.local.name = lvi.name;
			    info.local.type = lvi.type;
			}
		    }
		    info.local.size = 1;
		    switch (instr.getOpcode()) {
		    case opc_lload: case opc_dload:
			info.local.size = 2;
			/* fall through */
		    case opc_iload: case opc_fload: case opc_aload:
		    case opc_iinc:
			/* this is a load instruction */
			info.nextReads[instr.getLocalSlot()] = info;
			changedInfos.add(info);
			break;

		    case opc_ret:
			/* this is a ret instruction */
			info.usedBySub = new BitSet();
			info.nextReads[instr.getLocalSlot()] = info;
			changedInfos.add(info);
			break;

		    case opc_lstore: case opc_dstore:
			info.local.size = 2;
		    //case opc_istore: case opc_fstore: case opc_astore:
		    }
		}
		if (!i.hasNext())
		    break;
		info = info.nextInfo = new InstrInfo();
	    }
	}

	/* find out which locals are the same.
	 */
	while (!changedInfos.isEmpty()) {
	    InstrInfo info = changedInfos.remove();
	    Instruction instr = info.instr;

	    /* Mark the local as used in all ret instructions */
	    if (instr.hasLocalSlot()) {
		int slot = instr.getLocalSlot();
		for (int i=0; i< maxlocals; i++) {
		    InstrInfo retInfo = info.nextReads[i];
		    if (retInfo != null 
			&& retInfo.instr.getOpcode() == opc_ret
			&& !retInfo.usedBySub.get(slot)) {
			retInfo.usedBySub.set(slot);
			if (retInfo.jsrTargetInfo != null)
			    changedInfos.add(retInfo.jsrTargetInfo);
		    }
		}
	    }

	    Instruction prevInstr = instr.getPrevByAddr();
	    if (prevInstr != null) {
		if (!prevInstr.doesAlwaysJump())
		    promoteReads(info, prevInstr);
		else if (prevInstr.getOpcode() == opc_jsr) {
		    /* Prev instr is a jsr, promote reads to the
		     * corresponding ret.
		     */
		    InstrInfo jsrInfo = 
			(InstrInfo) instrInfos.get(prevInstr.getSingleSucc());
		    if (jsrInfo.retInfo != null) {
			/* Now promote reads that are modified by the
			 * subroutine to the ret, and those that are not
			 * to the jsr instruction.
			 */
			promoteReads(info, jsrInfo.retInfo.instr,
				     jsrInfo.retInfo.usedBySub, false);
			promoteReads(info, prevInstr, 
				     jsrInfo.retInfo.usedBySub, true);
		    }
		}
	    }

	    if (instr.getPreds() != null) {
		for (int i = 0; i < instr.getPreds().length; i++) {
		    Instruction predInstr = instr.getPreds()[i];
		    if (instr.getPreds()[i].getOpcode() == opc_jsr) {
			/* This is the target of a jsr instr.
			 */
			if (info.instr.getOpcode() != opc_astore) {
			    /* XXX Grrr, the bytecode verifier doesn't
			     * test if a jsr starts with astore.  So
			     * it is possible to do something else
			     * before putting the ret address into a
			     * local.  */
			    throw new AssertError("Non standard jsr");