localoptimizer.java

Java Optimize and Decompile Environment 源代码

			}
			InstrInfo retInfo = info.nextInfo.nextReads
			    [info.instr.getLocalSlot()];

			if (retInfo != null) {
			    if (retInfo.instr.getOpcode() != opc_ret)
				throw new AssertError
				    ("reading return address");

			    info.retInfo = retInfo;
			    retInfo.jsrTargetInfo = info;

			    /* Now promote reads from the instruction
			     * after the jsr to the ret instruction if
			     * they are modified by the subroutine,
			     * and to the jsr instruction otherwise.  
			     */
			    Instruction nextInstr = predInstr.getNextByAddr();
			    InstrInfo nextInfo 
				= (InstrInfo) instrInfos.get(nextInstr);

			    promoteReads(nextInfo, retInfo.instr,
					 retInfo.usedBySub, false);

			    promoteReads(nextInfo, predInstr, 
					 retInfo.usedBySub, true);
			}
		    }
		    promoteReads(info, instr.getPreds()[i]);
		}
	    }

	    for (int i=0; i < handlers.length; i++) {
		if (handlers[i].catcher == instr) {
		    for (Instruction preInstr = handlers[i].start;
			 preInstr != handlers[i].end.getNextByAddr(); 
			 preInstr = preInstr.getNextByAddr()) {
			promoteReads(info, preInstr);
		    }
		}
	    }
	}
	changedInfos = null;

	/* Now merge with the parameters
	 * The params should be the locals in firstInfo.nextReads
	 */
	for (int i=0; i< paramLocals.length; i++) {
	    if (firstInfo.nextReads[i] != null) {
		firstInfo.nextReads[i].local.combineInto(paramLocals[i]);
		paramLocals[i] = paramLocals[i].getReal();
	    }
	}
    }

    public void stripLocals() {
	ListIterator iter = bc.getInstructions().listIterator(); 
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    Instruction instr = (Instruction) iter.next();
	    if (info.local != null && info.local.usingInstrs.size() == 1) {
		/* If this is a store, whose value is never read; it can
                 * be removed, i.e replaced by a pop. */
		switch (instr.getOpcode()) {
		case opc_istore:
		case opc_fstore:
		case opc_astore:
		    iter.set(new Instruction(opc_pop));
		    break;
		case opc_lstore:
		case opc_dstore:
		    iter.set(new Instruction(opc_pop2));
		    break;
		default:
		}
	    }
	}
    }

    void distributeLocals(Vector locals) {
	if (locals.size() == 0)
	    return;

	/* Find the local with the least conflicts. */
	int min = Integer.MAX_VALUE;
	LocalInfo bestLocal = null;
	Enumeration enum = locals.elements();
	while (enum.hasMoreElements()) {
	    LocalInfo li = (LocalInfo) enum.nextElement();
	    int conflicts = 0;
	    Enumeration conflenum = li.conflictingLocals.elements();
	    while (conflenum.hasMoreElements()) {
		if (((LocalInfo)conflenum.nextElement()).newSlot != -2)
		    conflicts++;
	    }
	    if (conflicts < min) {
		min = conflicts;
		bestLocal = li;
	    }
	}
	/* Mark the local as taken */
	locals.removeElement(bestLocal);
	bestLocal.newSlot = -2;
	/* Now distribute the remaining locals recursively. */
	distributeLocals(locals);

	/* Finally find a new slot */
    next_slot:
	for (int slot = 0; ; slot++) {
	    Enumeration conflenum = bestLocal.conflictingLocals.elements();
	    while (conflenum.hasMoreElements()) {
		LocalInfo conflLocal = (LocalInfo)conflenum.nextElement();
		if (bestLocal.size == 2 && conflLocal.newSlot == slot+1) {
		    slot++;
		    continue next_slot;
		}
		if (conflLocal.size == 2 && conflLocal.newSlot+1 == slot)
		    continue next_slot;
		if (conflLocal.newSlot == slot) {
		    if (conflLocal.size == 2)
			slot++;
		    continue next_slot;
		}
	    }
	    bestLocal.newSlot = slot;
	    break;
	}
    }
    
    public void distributeLocals() {
	/* give locals new slots.  This is a graph coloring 
	 * algorithm (the optimal solution is NP complete, but this
	 * should be a good approximation).
	 */

	/* first give the params the same slot as they had before.
	 */
	for (int i=0; i<paramLocals.length; i++)
	    if (paramLocals[i] != null)
		paramLocals[i].newSlot = i;

	/* Now calculate the conflict settings.
	 */
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    if (info.instr.getOpcode() >= BytecodeInfo.opc_istore
		&& info.instr.getOpcode() <= BytecodeInfo.opc_astore) {
		/* This is a store.  It conflicts with every local, whose
		 * value will be read without write.
		 *
		 * If this is inside a ret, it also conflicts with
		 * locals, that are not used inside, and where any jsr
		 * would conflict with.  
		 */
		for (int i=0; i < maxlocals; i++) {
		    if (i != info.instr.getLocalSlot()
			&& info.nextReads[i] != null)
			info.local.conflictsWith(info.nextReads[i].local);
		    if (info.nextInfo.nextReads[i] != null
			&& info.nextInfo.nextReads[i].jsrTargetInfo != null) {
			Instruction[] jsrs = info.nextInfo.nextReads[i]
			    .jsrTargetInfo.instr.getPreds();
			for (int j=0; j< jsrs.length; j++) {
			    InstrInfo jsrInfo 
				= (InstrInfo) instrInfos.get(jsrs[j]);
			    for (int k=0; k < maxlocals; k++) {
				if (!info.nextInfo.nextReads[i].usedBySub
				    .get(k)
				    && jsrInfo.nextReads[k] != null)
				    info.local.conflictsWith
					(jsrInfo.nextReads[k].local);
			    }
			}
		    }
		}
	    }
	}

	/* Now put the locals that need a color into a vector.
	 */
	Vector locals = new Vector();
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    if (info.local != null 
		&& info.local.newSlot == -1
		&& !locals.contains(info.local))
		locals.addElement(info.local);
	}

	/* Now distribute slots recursive.
	 */
	distributeLocals(locals);

	/* Update the instructions.
	 */
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    if (info.local != null)
		info.instr.setLocalSlot(info.local.newSlot);
	}

	/* Update LocalVariableTable
	 */
	if (produceLVT)
	    buildNewLVT();
    }

    private InstrInfo CONFLICT = new InstrInfo();

    boolean promoteLifeLocals(LocalInfo[] newLife, InstrInfo nextInfo) {
	if (nextInfo.lifeLocals == null) {
	    nextInfo.lifeLocals = (LocalInfo[]) newLife.clone();
	    return true;
	}
	boolean changed = false;
	for (int i=0; i< maxlocals; i++) {
	    LocalInfo local = nextInfo.lifeLocals[i];
	    if (local == null)
		/* A conflict has already happened, or this slot
		 * may not have been initialized. */
		continue;

	    local = local.getReal();
	    LocalInfo newLocal = newLife[i];
	    if (newLocal != null)
		newLocal = newLocal.getReal();
	    if (local != newLocal) {
		nextInfo.lifeLocals[i] = null;
		changed = true;
	    }
	}
	return changed;
    }

    public void buildNewLVT() {
	/* First we recalculate the usedBySub, to use the new local numbers.
	 */
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo)
	    if (info.usedBySub != null)
		info.usedBySub = new BitSet();
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    if (info.local != null) {
		for (int i=0; i < info.nextReads.length; i++) {
		    if (info.nextReads[i] != null 
			&& info.nextReads[i].instr.getOpcode() == opc_ret)
			info.nextReads[i].usedBySub.set(info.local.newSlot);
		}
	    }
	}

	/* Now we begin with the first Instruction and follow program flow.
	 * We remember which locals are life in lifeLocals.
	 */

	firstInfo.lifeLocals = new LocalInfo[maxlocals];
	for (int i=0; i < paramLocals.length; i++)
	    firstInfo.lifeLocals[i] = paramLocals[i];

	Stack changedInfo = new Stack();
	changedInfo.push(firstInfo);
	Handler[] handlers = bc.getExceptionHandlers();
	while (!changedInfo.isEmpty()) {
	    InstrInfo info = (InstrInfo) changedInfo.pop();
	    Instruction instr = info.instr;
	    LocalInfo[] newLife = info.lifeLocals;
	    if (instr.hasLocalSlot()) {
		int slot = instr.getLocalSlot();
		LocalInfo instrLocal = info.local.getReal();
		newLife = (LocalInfo[]) newLife.clone();
		newLife[slot] = instrLocal;
		if (instrLocal.name != null) {
		    for (int j=0; j< newLife.length; j++) {
			if (j != slot
			    && newLife[j] != null
			    && instrLocal.name.equals(newLife[j].name)) {
			    /* This local changed the slot. */
		 	   newLife[j] = null;
			}
		    }
		}
	    }
	    
	    if (!instr.doesAlwaysJump()) {
		InstrInfo nextInfo = info.nextInfo;
		if (promoteLifeLocals(newLife, nextInfo))
		    changedInfo.push(nextInfo);
	    } 
	    if (instr.hasSuccs()) {
		Instruction[] succs = instr.getSuccs();
		for (int i = 0; i < succs.length; i++) {
		    InstrInfo nextInfo
			= (InstrInfo) instrInfos.get(succs[i]);
		    if (promoteLifeLocals(newLife, nextInfo))
			changedInfo.push(nextInfo);
		}
	    }
	    for (int i=0; i < handlers.length; i++) {
		if (handlers[i].start.compareTo(instr) <= 0
		    && handlers[i].end.compareTo(instr) >= 0) {
		    InstrInfo nextInfo
			= (InstrInfo) instrInfos.get(handlers[i].catcher);
		    if (promoteLifeLocals(newLife, nextInfo))
			changedInfo.push(nextInfo);
		}
	    }

	    if (info.instr.getOpcode() == opc_jsr) {
		/* On a jsr we do a special merge */

		Instruction jsrTargetInstr = info.instr.getSingleSucc();
		InstrInfo jsrTargetInfo
		    = (InstrInfo) instrInfos.get(jsrTargetInstr);
		InstrInfo retInfo = jsrTargetInfo.retInfo;
		if (retInfo != null && retInfo.lifeLocals != null) {
		    LocalInfo[] retLife = (LocalInfo[]) newLife.clone();
		    for (int i=0; i< maxlocals; i++) {
			if (retInfo.usedBySub.get(i))
			    retLife[i] = retInfo.lifeLocals[i];
		    }
		    if (promoteLifeLocals(retLife, info.nextInfo))
			changedInfo.push(info.nextInfo);
		}
	    }

	    if (info.jsrTargetInfo != null) {
		/* On a ret we do a special merge */

		Instruction jsrTargetInstr = info.jsrTargetInfo.instr;
		for (int j=0; j< jsrTargetInstr.getPreds().length; j++) {
		    InstrInfo jsrInfo
			= (InstrInfo) instrInfos.get(jsrTargetInstr.getPreds()[j]);

		    if (jsrInfo.lifeLocals == null)
			/* life locals are not calculated, yet */
			continue;
		    LocalInfo[] retLife = (LocalInfo[]) newLife.clone();
		    for (int i=0; i< maxlocals; i++) {
			if (!info.usedBySub.get(i))
			    retLife[i] = jsrInfo.lifeLocals[i];
		    }
		    if (promoteLifeLocals(retLife, jsrInfo.nextInfo))
			changedInfo.push(jsrInfo.nextInfo);
		}
	    }
	}

	Vector lvtEntries = new Vector();
	LocalVariableInfo[] lvi = new LocalVariableInfo[maxlocals];
	LocalInfo[] currentLocal = new LocalInfo[maxlocals];
	for (int i=0; i< paramLocals.length; i++) {
	    if (paramLocals[i] != null) {
		currentLocal[i] = paramLocals[i];
		if (currentLocal[i].name != null) {
		    lvi[i] = new LocalVariableInfo();
		    lvtEntries.addElement(lvi[i]);
		    lvi[i].name = currentLocal[i].name; /* XXX obfuscation? */
		    lvi[i].type = Main.getClassBundle()
			.getTypeAlias(currentLocal[i].type);
		    lvi[i].start = (Instruction) bc.getInstructions().get(0);
		    lvi[i].slot = i;
		}
	    }
	}
	Instruction lastInstr = null;
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    for (int i=0; i< maxlocals; i++) {
		LocalInfo lcl = info.lifeLocals != null ? info.lifeLocals[i]
		    : null;
		if (lcl != currentLocal[i]
		    && (lcl == null || currentLocal[i] == null
			|| lcl.name == null || lcl.type == null
			|| !lcl.name.equals(currentLocal[i].name)
			|| !lcl.type.equals(currentLocal[i].type))) {
		    if (lvi[i] != null) {
			lvi[i].end = info.instr.getPrevByAddr();
		    }
		    lvi[i] = null;
		    currentLocal[i] = lcl;
		    if (currentLocal[i] != null
			&& currentLocal[i].name != null
			&& currentLocal[i].type != null) {
			lvi[i] = new LocalVariableInfo();
			lvtEntries.addElement(lvi[i]);
			lvi[i].name = currentLocal[i].name;
			lvi[i].type = Main.getClassBundle()
			    .getTypeAlias(currentLocal[i].type);
			lvi[i].start = info.instr;
			lvi[i].slot = i;
		    }
		}
	    }
	    lastInstr = info.instr;
	}
	for (int i=0; i< maxlocals; i++) {
	    if (lvi[i] != null)
		lvi[i].end = lastInstr;
	}
	LocalVariableInfo[] lvt = new LocalVariableInfo[lvtEntries.size()];
	lvtEntries.copyInto(lvt);
	bc.setLocalVariableTable(lvt);
    }

    public void dumpLocals() {
	Vector locals = new Vector();
	for (InstrInfo info = firstInfo; info != null; info = info.nextInfo) {
	    GlobalOptions.err.println(info.instr.getDescription());
	    GlobalOptions.err.print("nextReads: ");
	    for (int i=0; i<maxlocals; i++)
		if (info.nextReads[i] == null)
		    GlobalOptions.err.print("-,");
		else
		    GlobalOptions.err.print(info.nextReads[i].instr.getAddr()+",");
	    if (info.usedBySub != null)
		GlobalOptions.err.print("  usedBySub: "+info.usedBySub);
	    if (info.retInfo != null)
		GlobalOptions.err.print("  ret info: "
					+info.retInfo.instr.getAddr());
	    if (info.jsrTargetInfo != null)
		GlobalOptions.err.print("  jsr info: "
					+info.jsrTargetInfo.instr.getAddr());

	    GlobalOptions.err.println();
	    if (info.local != null && !locals.contains(info.local))
		locals.addElement(info.local);
	}
	Enumeration enum = locals.elements();
	while (enum.hasMoreElements()) {
	    LocalInfo li = (LocalInfo) enum.nextElement();
	    int slot = ((InstrInfo)li.usingInstrs.elementAt(0))
		.instr.getLocalSlot();
	    GlobalOptions.err.print("Slot: "+slot+" conflicts:");
	    Enumeration enum1 = li.conflictingLocals.elements();
	    while (enum1.hasMoreElements()) {
		LocalInfo cfl = (LocalInfo)enum1.nextElement();
		GlobalOptions.err.print(cfl.getFirstAddr()+", ");
	    }
	    GlobalOptions.err.println();
	    GlobalOptions.err.print(li.getFirstAddr());
	    GlobalOptions.err.print("     instrs: ");
	    Enumeration enum2 = li.usingInstrs.elements();
	    while (enum2.hasMoreElements())
		GlobalOptions.err.print(((InstrInfo)enum2.nextElement())
					.instr.getAddr()+", ");
	    GlobalOptions.err.println();
	}
	GlobalOptions.err.println("-----------");
    }

    public void transformCode(BytecodeInfo bytecode) {
	this.bc = bytecode;
	calcLocalInfo();
	if ((GlobalOptions.debuggingFlags 
	     & GlobalOptions.DEBUG_LOCALS) != 0) {
	    GlobalOptions.err.println("Before Local Optimization: ");
	    dumpLocals();
	}
	stripLocals();
	distributeLocals();
	
	if ((GlobalOptions.debuggingFlags 
	     & GlobalOptions.DEBUG_LOCALS) != 0) {
	    GlobalOptions.err.println("After Local Optimization: ");
	    dumpLocals();
	}

	firstInfo = null;
	changedInfos = null;
	instrInfos = null;
	paramLocals = null;
    }
}