/* * Copyright (C) 2007 The Android Open Source Project * * 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 com.android.dx.cf.code; import com.android.dx.cf.iface.MethodList; import com.android.dx.rop.code.AccessFlags; import com.android.dx.rop.code.BasicBlock; import com.android.dx.rop.code.BasicBlockList; import com.android.dx.rop.code.Insn; import com.android.dx.rop.code.InsnList; import com.android.dx.rop.code.PlainCstInsn; import com.android.dx.rop.code.PlainInsn; import com.android.dx.rop.code.RegisterSpec; import com.android.dx.rop.code.RegisterSpecList; import com.android.dx.rop.code.Rop; import com.android.dx.rop.code.RopMethod; import com.android.dx.rop.code.Rops; import com.android.dx.rop.code.SourcePosition; import com.android.dx.rop.code.ThrowingCstInsn; import com.android.dx.rop.code.ThrowingInsn; import com.android.dx.rop.code.TranslationAdvice; import com.android.dx.rop.cst.CstInteger; import com.android.dx.rop.cst.CstType; import com.android.dx.rop.type.Prototype; import com.android.dx.rop.type.StdTypeList; import com.android.dx.rop.type.Type; import com.android.dx.rop.type.TypeList; import com.android.dx.util.Bits; import com.android.dx.util.Hex; import com.android.dx.util.IntList; import java.util.ArrayList; import java.util.BitSet; import java.util.Collection; import java.util.HashMap; import java.util.Map; /** * Utility that converts a basic block list into a list of register-oriented * blocks. */ public final class Ropper { /** label offset for the parameter assignment block */ private static final int PARAM_ASSIGNMENT = -1; /** label offset for the return block */ private static final int RETURN = -2; /** label offset for the synchronized method final return block */ private static final int SYNCH_RETURN = -3; /** label offset for the first synchronized method setup block */ private static final int SYNCH_SETUP_1 = -4; /** label offset for the second synchronized method setup block */ private static final int SYNCH_SETUP_2 = -5; /** * label offset for the first synchronized method exception * handler block */ private static final int SYNCH_CATCH_1 = -6; /** * label offset for the second synchronized method exception * handler block */ private static final int SYNCH_CATCH_2 = -7; /** number of special label offsets */ private static final int SPECIAL_LABEL_COUNT = 7; /** {@code non-null;} method being converted */ private final ConcreteMethod method; /** {@code non-null;} original block list */ private final ByteBlockList blocks; /** max locals of the method */ private final int maxLocals; /** max label (exclusive) of any original bytecode block */ private final int maxLabel; /** {@code non-null;} simulation machine to use */ private final RopperMachine machine; /** {@code non-null;} simulator to use */ private final Simulator sim; /** * {@code non-null;} sparse array mapping block labels to initial frame * contents, if known */ private final Frame[] startFrames; /** {@code non-null;} output block list in-progress */ private final ArrayList result; /** * {@code non-null;} list of subroutine-nest labels * (See {@link Frame#getSubroutines} associated with each result block. * Parallel to {@link Ropper#result}. */ private final ArrayList resultSubroutines; /** * {@code non-null;} for each block (by label) that is used as an exception * handler in the input, the exception handling info in Rop. */ private final CatchInfo[] catchInfos; /** * whether an exception-handler block for a synchronized method was * ever required */ private boolean synchNeedsExceptionHandler; /** * {@code non-null;} list of subroutines indexed by label of start * address */ private final Subroutine[] subroutines; /** true if {@code subroutines} is non-empty */ private boolean hasSubroutines; /** Allocates labels of exception handler setup blocks. */ private final ExceptionSetupLabelAllocator exceptionSetupLabelAllocator; /** * Keeps mapping of an input exception handler target code and how it is generated/targeted in * Rop. */ private class CatchInfo { /** * {@code non-null;} map of ExceptionHandlerSetup by the type they handle */ private final Map setups = new HashMap(); /** * Get the {@link ExceptionHandlerSetup} corresponding to the given type. The * ExceptionHandlerSetup is created if this the first request for the given type. * * @param caughtType {@code non-null;} the type catch by the requested setup * @return {@code non-null;} the handler setup block info for the given type */ ExceptionHandlerSetup getSetup(Type caughtType) { ExceptionHandlerSetup handler = setups.get(caughtType); if (handler == null) { int handlerSetupLabel = exceptionSetupLabelAllocator.getNextLabel(); handler = new ExceptionHandlerSetup(caughtType, handlerSetupLabel); setups.put(caughtType, handler); } return handler; } /** * Get all {@link ExceptionHandlerSetup} of this handler. * * @return {@code non-null;} */ Collection getSetups() { return setups.values(); } } /** * Keeps track of an exception handler setup. */ private static class ExceptionHandlerSetup { /** * {@code non-null;} The caught type. */ private Type caughtType; /** * {@code >= 0;} The label of the exception setup block. */ private int label; /** * Constructs instance. * * @param caughtType {@code non-null;} the caught type * @param label {@code >= 0;} the label */ ExceptionHandlerSetup(Type caughtType, int label) { this.caughtType = caughtType; this.label = label; } /** * @return {@code non-null;} the caught type */ Type getCaughtType() { return caughtType; } /** * @return {@code >= 0;} the label */ public int getLabel() { return label; } } /** * Keeps track of subroutines that exist in java form and are inlined in * Rop form. */ private class Subroutine { /** list of all blocks that jsr to this subroutine */ private BitSet callerBlocks; /** List of all blocks that return from this subroutine */ private BitSet retBlocks; /** first block in this subroutine */ private int startBlock; /** * Constructs instance. * * @param startBlock First block of the subroutine. */ Subroutine(int startBlock) { this.startBlock = startBlock; retBlocks = new BitSet(maxLabel); callerBlocks = new BitSet(maxLabel); hasSubroutines = true; } /** * Constructs instance. * * @param startBlock First block of the subroutine. * @param retBlock one of the ret blocks (final blocks) of this * subroutine. */ Subroutine(int startBlock, int retBlock) { this(startBlock); addRetBlock(retBlock); } /** * @return {@code >= 0;} the label of the subroutine's start block. */ int getStartBlock() { return startBlock; } /** * Adds a label to the list of ret blocks (final blocks) for this * subroutine. * * @param retBlock ret block label */ void addRetBlock(int retBlock) { retBlocks.set(retBlock); } /** * Adds a label to the list of caller blocks for this subroutine. * * @param label a block that invokes this subroutine. */ void addCallerBlock(int label) { callerBlocks.set(label); } /** * Generates a list of subroutine successors. Note: successor blocks * could be listed more than once. This is ok, because this successor * list (and the block it's associated with) will be copied and inlined * before we leave the ropper. Redundent successors will result in * redundent (no-op) merges. * * @return all currently known successors * (return destinations) for that subroutine */ IntList getSuccessors() { IntList successors = new IntList(callerBlocks.size()); /* * For each subroutine caller, get it's target. If the * target is us, add the ret target (subroutine successor) * to our list */ for (int label = callerBlocks.nextSetBit(0); label >= 0; label = callerBlocks.nextSetBit(label+1)) { BasicBlock subCaller = labelToBlock(label); successors.add(subCaller.getSuccessors().get(0)); } successors.setImmutable(); return successors; } /** * Merges the specified frame into this subroutine's successors, * setting {@code workSet} as appropriate. To be called with * the frame of a subroutine ret block. * * @param frame {@code non-null;} frame from ret block to merge * @param workSet {@code non-null;} workset to update */ void mergeToSuccessors(Frame frame, int[] workSet) { for (int label = callerBlocks.nextSetBit(0); label >= 0; label = callerBlocks.nextSetBit(label+1)) { BasicBlock subCaller = labelToBlock(label); int succLabel = subCaller.getSuccessors().get(0); Frame subFrame = frame.subFrameForLabel(startBlock, label); if (subFrame != null) { mergeAndWorkAsNecessary(succLabel, -1, null, subFrame, workSet); } else { Bits.set(workSet, label); } } } } /** * Converts a {@link ConcreteMethod} to a {@link RopMethod}. * * @param method {@code non-null;} method to convert * @param advice {@code non-null;} translation advice to use * @param methods {@code non-null;} list of methods defined by the class * that defines {@code method}. * @return {@code non-null;} the converted instance */ public static RopMethod convert(ConcreteMethod method, TranslationAdvice advice, MethodList methods) { try { Ropper r = new Ropper(method, advice, methods); r.doit(); return r.getRopMethod(); } catch (SimException ex) { ex.addContext("...while working on method " + method.getNat().toHuman()); throw ex; } } /** * Constructs an instance. This class is not publicly instantiable; use * {@link #convert}. * * @param method {@code non-null;} method to convert * @param advice {@code non-null;} translation advice to use * @param methods {@code non-null;} list of methods defined by the class * that defines {@code method}. */ private Ropper(ConcreteMethod method, TranslationAdvice advice, MethodList methods) { if (method == null) { throw new NullPointerException("method == null"); } if (advice == null) { throw new NullPointerException("advice == null"); } this.method = method; this.blocks = BasicBlocker.identifyBlocks(method); this.maxLabel = blocks.getMaxLabel(); this.maxLocals = method.getMaxLocals(); this.machine = new RopperMachine(this, method, advice, methods); this.sim = new Simulator(machine, method); this.startFrames = new Frame[maxLabel]; this.subroutines = new Subroutine[maxLabel]; /* * The "* 2 + 10" below is to conservatively believe that every * block is an exception handler target and should also * take care of enough other possible extra overhead such that * the underlying array is unlikely to need resizing. */ this.result = new ArrayList(blocks.size() * 2 + 10); this.resultSubroutines = new ArrayList(blocks.size() * 2 + 10); this.catchInfos = new CatchInfo[maxLabel]; this.synchNeedsExceptionHandler = false; /* * Set up the first stack frame with the right limits, but leave it * empty here (to be filled in outside of the constructor). */ startFrames[0] = new Frame(maxLocals, method.getMaxStack()); exceptionSetupLabelAllocator = new ExceptionSetupLabelAllocator(); } /** * Gets the first (lowest) register number to use as the temporary * area when unwinding stack manipulation ops. * * @return {@code >= 0;} the first register to use */ /*package*/ int getFirstTempStackReg() { /* * We use the register that is just past the deepest possible * stack element, plus one if the method is synchronized to * avoid overlapping with the synch register. We don't need to * do anything else special at this level, since later passes * will merely notice the highest register used by explicit * inspection. */ int regCount = getNormalRegCount(); return isSynchronized() ? regCount + 1 : regCount; } /** * Gets the label for the given special-purpose block. The given label * should be one of the static constants defined by this class. * * @param label {@code < 0;} the special label constant * @return {@code >= 0;} the actual label value to use */ private int getSpecialLabel(int label) { /* * The label is bitwise-complemented so that mistakes where * LABEL is used instead of getSpecialLabel(LABEL) cause a * failure at block construction time, since negative labels * are illegal. 0..maxLabel (exclusive) are the original blocks and * maxLabel..(maxLabel + method.getCatches().size()) are reserved for exception handler * setup blocks (see getAvailableLabel(), exceptionSetupLabelAllocator). */ return maxLabel + method.getCatches().size() + ~label; } /** * Gets the minimum label for unreserved use. * * @return {@code >= 0;} the minimum label */ private int getMinimumUnreservedLabel() { /* * The labels below (maxLabel + method.getCatches().size() + SPECIAL_LABEL_COUNT) are * reserved for particular uses. */ return maxLabel + method.getCatches().size() + SPECIAL_LABEL_COUNT; } /** * Gets an unreserved and available label. * Labels are distributed this way: *
    *
  • [0, maxLabel[ are the labels of the blocks directly * corresponding to the input bytecode.
  • *
  • [maxLabel, maxLabel + method.getCatches().size()[ are reserved for exception setup * blocks.
  • *
  • [maxLabel + method.getCatches().size(), * maxLabel + method.getCatches().size() + SPECIAL_LABEL_COUNT[ are reserved for special blocks, * ie param assignement, return and synch blocks.
  • *
  • [maxLabel method.getCatches().size() + SPECIAL_LABEL_COUNT, getAvailableLabel()[ assigned * labels. Note that some * of the assigned labels may not be used any more if they were assigned to a block that was * deleted since.
  • *
* * @return {@code >= 0;} an available label with the guaranty that all greater labels are * also available. */ private int getAvailableLabel() { int candidate = getMinimumUnreservedLabel(); for (BasicBlock bb : result) { int label = bb.getLabel(); if (label >= candidate) { candidate = label + 1; } } return candidate; } /** * Gets whether the method being translated is synchronized. * * @return whether the method being translated is synchronized */ private boolean isSynchronized() { int accessFlags = method.getAccessFlags(); return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0; } /** * Gets whether the method being translated is static. * * @return whether the method being translated is static */ private boolean isStatic() { int accessFlags = method.getAccessFlags(); return (accessFlags & AccessFlags.ACC_STATIC) != 0; } /** * Gets the total number of registers used for "normal" purposes (i.e., * for the straightforward translation from the original Java). * * @return {@code >= 0;} the total number of registers used */ private int getNormalRegCount() { return maxLocals + method.getMaxStack(); } /** * Gets the register spec to use to hold the object to synchronize on, * for a synchronized method. * * @return {@code non-null;} the register spec */ private RegisterSpec getSynchReg() { /* * We use the register that is just past the deepest possible * stack element, with a minimum of v1 since v0 is what's * always used to hold the caught exception when unwinding. We * don't need to do anything else special at this level, since * later passes will merely notice the highest register used * by explicit inspection. */ int reg = getNormalRegCount(); return RegisterSpec.make((reg < 1) ? 1 : reg, Type.OBJECT); } /** * Searches {@link #result} for a block with the given label. Returns its * index if found, or returns {@code -1} if there is no such block. * * @param label the label to look for * @return {@code >= -1;} the index for the block with the given label or * {@code -1} if there is no such block */ private int labelToResultIndex(int label) { int sz = result.size(); for (int i = 0; i < sz; i++) { BasicBlock one = result.get(i); if (one.getLabel() == label) { return i; } } return -1; } /** * Searches {@link #result} for a block with the given label. Returns it if * found, or throws an exception if there is no such block. * * @param label the label to look for * @return {@code non-null;} the block with the given label */ private BasicBlock labelToBlock(int label) { int idx = labelToResultIndex(label); if (idx < 0) { throw new IllegalArgumentException("no such label " + Hex.u2(label)); } return result.get(idx); } /** * Adds a block to the output result. * * @param block {@code non-null;} the block to add * @param subroutines {@code non-null;} subroutine label list * as described in {@link Frame#getSubroutines} */ private void addBlock(BasicBlock block, IntList subroutines) { if (block == null) { throw new NullPointerException("block == null"); } result.add(block); subroutines.throwIfMutable(); resultSubroutines.add(subroutines); } /** * Adds or replace a block in the output result. If this is a * replacement, then any extra blocks that got added with the * original get removed as a result of calling this method. * * @param block {@code non-null;} the block to add or replace * @param subroutines {@code non-null;} subroutine label list * as described in {@link Frame#getSubroutines} * @return {@code true} if the block was replaced or * {@code false} if it was added for the first time */ private boolean addOrReplaceBlock(BasicBlock block, IntList subroutines) { if (block == null) { throw new NullPointerException("block == null"); } int idx = labelToResultIndex(block.getLabel()); boolean ret; if (idx < 0) { ret = false; } else { /* * We are replacing a pre-existing block, so find any * blocks that got added as part of the original and * remove those too. Such blocks are (possibly indirect) * successors of this block which are out of the range of * normally-translated blocks. */ removeBlockAndSpecialSuccessors(idx); ret = true; } result.add(block); subroutines.throwIfMutable(); resultSubroutines.add(subroutines); return ret; } /** * Adds or replaces a block in the output result. Do not delete * any successors. * * @param block {@code non-null;} the block to add or replace * @param subroutines {@code non-null;} subroutine label list * as described in {@link Frame#getSubroutines} * @return {@code true} if the block was replaced or * {@code false} if it was added for the first time */ private boolean addOrReplaceBlockNoDelete(BasicBlock block, IntList subroutines) { if (block == null) { throw new NullPointerException("block == null"); } int idx = labelToResultIndex(block.getLabel()); boolean ret; if (idx < 0) { ret = false; } else { result.remove(idx); resultSubroutines.remove(idx); ret = true; } result.add(block); subroutines.throwIfMutable(); resultSubroutines.add(subroutines); return ret; } /** * Helper for {@link #addOrReplaceBlock} which recursively removes * the given block and all blocks that are (direct and indirect) * successors of it whose labels indicate that they are not in the * normally-translated range. * * @param idx {@code non-null;} block to remove (etc.) */ private void removeBlockAndSpecialSuccessors(int idx) { int minLabel = getMinimumUnreservedLabel(); BasicBlock block = result.get(idx); IntList successors = block.getSuccessors(); int sz = successors.size(); result.remove(idx); resultSubroutines.remove(idx); for (int i = 0; i < sz; i++) { int label = successors.get(i); if (label >= minLabel) { idx = labelToResultIndex(label); if (idx < 0) { throw new RuntimeException("Invalid label " + Hex.u2(label)); } removeBlockAndSpecialSuccessors(idx); } } } /** * Extracts the resulting {@link RopMethod} from the instance. * * @return {@code non-null;} the method object */ private RopMethod getRopMethod() { // Construct the final list of blocks. int sz = result.size(); BasicBlockList bbl = new BasicBlockList(sz); for (int i = 0; i < sz; i++) { bbl.set(i, result.get(i)); } bbl.setImmutable(); // Construct the method object to wrap it all up. /* * Note: The parameter assignment block is always the first * that should be executed, hence the second argument to the * constructor. */ return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT)); } /** * Does the conversion. */ private void doit() { int[] workSet = Bits.makeBitSet(maxLabel); Bits.set(workSet, 0); addSetupBlocks(); setFirstFrame(); for (;;) { int offset = Bits.findFirst(workSet, 0); if (offset < 0) { break; } Bits.clear(workSet, offset); ByteBlock block = blocks.labelToBlock(offset); Frame frame = startFrames[offset]; try { processBlock(block, frame, workSet); } catch (SimException ex) { ex.addContext("...while working on block " + Hex.u2(offset)); throw ex; } } addReturnBlock(); addSynchExceptionHandlerBlock(); addExceptionSetupBlocks(); if (hasSubroutines) { // Subroutines are very rare, so skip this step if it's n/a inlineSubroutines(); } } /** * Sets up the first frame to contain all the incoming parameters in * locals. */ private void setFirstFrame() { Prototype desc = method.getEffectiveDescriptor(); startFrames[0].initializeWithParameters(desc.getParameterTypes()); startFrames[0].setImmutable(); } /** * Processes the given block. * * @param block {@code non-null;} block to process * @param frame {@code non-null;} start frame for the block * @param workSet {@code non-null;} bits representing work to do, * which this method may add to */ private void processBlock(ByteBlock block, Frame frame, int[] workSet) { // Prepare the list of caught exceptions for this block. ByteCatchList catches = block.getCatches(); machine.startBlock(catches.toRopCatchList()); /* * Using a copy of the given frame, simulate each instruction, * calling into machine for each. */ frame = frame.copy(); sim.simulate(block, frame); frame.setImmutable(); int extraBlockCount = machine.getExtraBlockCount(); ArrayList insns = machine.getInsns(); int insnSz = insns.size(); /* * Merge the frame into each possible non-exceptional * successor. */ int catchSz = catches.size(); IntList successors = block.getSuccessors(); int startSuccessorIndex; Subroutine calledSubroutine = null; if (machine.hasJsr()) { /* * If this frame ends in a JSR, only merge our frame with * the subroutine start, not the subroutine's return target. */ startSuccessorIndex = 1; int subroutineLabel = successors.get(1); if (subroutines[subroutineLabel] == null) { subroutines[subroutineLabel] = new Subroutine (subroutineLabel); } subroutines[subroutineLabel].addCallerBlock(block.getLabel()); calledSubroutine = subroutines[subroutineLabel]; } else if (machine.hasRet()) { /* * This block ends in a ret, which means it's the final block * in some subroutine. Ultimately, this block will be copied * and inlined for each call and then disposed of. */ ReturnAddress ra = machine.getReturnAddress(); int subroutineLabel = ra.getSubroutineAddress(); if (subroutines[subroutineLabel] == null) { subroutines[subroutineLabel] = new Subroutine (subroutineLabel, block.getLabel()); } else { subroutines[subroutineLabel].addRetBlock(block.getLabel()); } successors = subroutines[subroutineLabel].getSuccessors(); subroutines[subroutineLabel] .mergeToSuccessors(frame, workSet); // Skip processing below since we just did it. startSuccessorIndex = successors.size(); } else if (machine.wereCatchesUsed()) { /* * If there are catches, then the first successors * (which will either be all of them or all but the last one) * are catch targets. */ startSuccessorIndex = catchSz; } else { startSuccessorIndex = 0; } int succSz = successors.size(); for (int i = startSuccessorIndex; i < succSz; i++) { int succ = successors.get(i); try { mergeAndWorkAsNecessary(succ, block.getLabel(), calledSubroutine, frame, workSet); } catch (SimException ex) { ex.addContext("...while merging to block " + Hex.u2(succ)); throw ex; } } if ((succSz == 0) && machine.returns()) { /* * The block originally contained a return, but it has * been made to instead end with a goto, and we need to * tell it at this point that its sole successor is the * return block. This has to happen after the merge loop * above, since, at this point, the return block doesn't * actually exist; it gets synthesized at the end of * processing the original blocks. */ successors = IntList.makeImmutable(getSpecialLabel(RETURN)); succSz = 1; } int primarySucc; if (succSz == 0) { primarySucc = -1; } else { primarySucc = machine.getPrimarySuccessorIndex(); if (primarySucc >= 0) { primarySucc = successors.get(primarySucc); } } /* * This variable is true only when the method is synchronized and * the block being processed can possibly throw an exception. */ boolean synch = isSynchronized() && machine.canThrow(); if (synch || (catchSz != 0)) { /* * Deal with exception handlers: Merge an exception-catch * frame into each possible exception handler, and * construct a new set of successors to point at the * exception handler setup blocks (which get synthesized * at the very end of processing). */ boolean catchesAny = false; IntList newSucc = new IntList(succSz); for (int i = 0; i < catchSz; i++) { ByteCatchList.Item one = catches.get(i); CstType exceptionClass = one.getExceptionClass(); int targ = one.getHandlerPc(); catchesAny |= (exceptionClass == CstType.OBJECT); Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass); try { mergeAndWorkAsNecessary(targ, block.getLabel(), null, f, workSet); } catch (SimException ex) { ex.addContext("...while merging exception to block " + Hex.u2(targ)); throw ex; } /* * Set up the exception handler type. */ CatchInfo handlers = catchInfos[targ]; if (handlers == null) { handlers = new CatchInfo(); catchInfos[targ] = handlers; } ExceptionHandlerSetup handler = handlers.getSetup(exceptionClass.getClassType()); /* * The synthesized exception setup block will have the label given by handler. */ newSucc.add(handler.getLabel()); } if (synch && !catchesAny) { /* * The method is synchronized and this block doesn't * already have a catch-all handler, so add one to the * end, both in the successors and in the throwing * instruction(s) at the end of the block (which is where * the caught classes live). */ newSucc.add(getSpecialLabel(SYNCH_CATCH_1)); synchNeedsExceptionHandler = true; for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) { Insn insn = insns.get(i); if (insn.canThrow()) { insn = insn.withAddedCatch(Type.OBJECT); insns.set(i, insn); } } } if (primarySucc >= 0) { newSucc.add(primarySucc); } newSucc.setImmutable(); successors = newSucc; } // Construct the final resulting block(s), and store it (them). int primarySuccListIndex = successors.indexOf(primarySucc); /* * If there are any extra blocks, work backwards through the * list of instructions, adding single-instruction blocks, and * resetting the successors variables as appropriate. */ for (/*extraBlockCount*/; extraBlockCount > 0; extraBlockCount--) { /* * Some of the blocks that the RopperMachine wants added * are for move-result insns, and these need goto insns as well. */ Insn extraInsn = insns.get(--insnSz); boolean needsGoto = extraInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE; InsnList il = new InsnList(needsGoto ? 2 : 1); IntList extraBlockSuccessors = successors; il.set(0, extraInsn); if (needsGoto) { il.set(1, new PlainInsn(Rops.GOTO, extraInsn.getPosition(), null, RegisterSpecList.EMPTY)); /* * Obviously, this block won't be throwing an exception * so it should only have one successor. */ extraBlockSuccessors = IntList.makeImmutable(primarySucc); } il.setImmutable(); int label = getAvailableLabel(); BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors, primarySucc); // All of these extra blocks will be in the same subroutine addBlock(bb, frame.getSubroutines()); successors = successors.mutableCopy(); successors.set(primarySuccListIndex, label); successors.setImmutable(); primarySucc = label; } Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1); /* * Add a goto to the end of the block if it doesn't already * end with a branch, to maintain the invariant that all * blocks end with a branch of some sort or other. Note that * it is possible for there to be blocks for which no * instructions were ever output (e.g., only consist of pop* * in the original Java bytecode). */ if ((lastInsn == null) || (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) { SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO : lastInsn.getPosition(); insns.add(new PlainInsn(Rops.GOTO, pos, null, RegisterSpecList.EMPTY)); insnSz++; } /* * Construct a block for the remaining instructions (which in * the usual case is all of them). */ InsnList il = new InsnList(insnSz); for (int i = 0; i < insnSz; i++) { il.set(i, insns.get(i)); } il.setImmutable(); BasicBlock bb = new BasicBlock(block.getLabel(), il, successors, primarySucc); addOrReplaceBlock(bb, frame.getSubroutines()); } /** * Helper for {@link #processBlock}, which merges frames and * adds to the work set, as necessary. * * @param label {@code >= 0;} label to work on * @param pred predecessor label; must be {@code >= 0} when * {@code label} is a subroutine start block and calledSubroutine * is non-null. Otherwise, may be -1. * @param calledSubroutine {@code null-ok;} a Subroutine instance if * {@code label} is the first block in a subroutine. * @param frame {@code non-null;} new frame for the labelled block * @param workSet {@code non-null;} bits representing work to do, * which this method may add to */ private void mergeAndWorkAsNecessary(int label, int pred, Subroutine calledSubroutine, Frame frame, int[] workSet) { Frame existing = startFrames[label]; Frame merged; if (existing != null) { /* * Some other block also continues at this label. Merge * the frames, and re-set the bit in the work set if there * was a change. */ if (calledSubroutine != null) { merged = existing.mergeWithSubroutineCaller(frame, calledSubroutine.getStartBlock(), pred); } else { merged = existing.mergeWith(frame); } if (merged != existing) { startFrames[label] = merged; Bits.set(workSet, label); } } else { // This is the first time this label has been encountered. if (calledSubroutine != null) { startFrames[label] = frame.makeNewSubroutineStartFrame(label, pred); } else { startFrames[label] = frame; } Bits.set(workSet, label); } } /** * Constructs and adds the blocks that perform setup for the rest of * the method. This includes a first block which merely contains * assignments from parameters to the same-numbered registers and * a possible second block which deals with synchronization. */ private void addSetupBlocks() { LocalVariableList localVariables = method.getLocalVariables(); SourcePosition pos = method.makeSourcePosistion(0); Prototype desc = method.getEffectiveDescriptor(); StdTypeList params = desc.getParameterTypes(); int sz = params.size(); InsnList insns = new InsnList(sz + 1); int at = 0; for (int i = 0; i < sz; i++) { Type one = params.get(i); LocalVariableList.Item local = localVariables.pcAndIndexToLocal(0, at); RegisterSpec result = (local == null) ? RegisterSpec.make(at, one) : RegisterSpec.makeLocalOptional(at, one, local.getLocalItem()); Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result, RegisterSpecList.EMPTY, CstInteger.make(at)); insns.set(i, insn); at += one.getCategory(); } insns.set(sz, new PlainInsn(Rops.GOTO, pos, null, RegisterSpecList.EMPTY)); insns.setImmutable(); boolean synch = isSynchronized(); int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0; BasicBlock bb = new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT), insns, IntList.makeImmutable(label), label); addBlock(bb, IntList.EMPTY); if (synch) { RegisterSpec synchReg = getSynchReg(); Insn insn; if (isStatic()) { insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos, RegisterSpecList.EMPTY, StdTypeList.EMPTY, method.getDefiningClass()); insns = new InsnList(1); insns.set(0, insn); } else { insns = new InsnList(2); insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos, synchReg, RegisterSpecList.EMPTY, CstInteger.VALUE_0); insns.set(0, insn); insns.set(1, new PlainInsn(Rops.GOTO, pos, null, RegisterSpecList.EMPTY)); } int label2 = getSpecialLabel(SYNCH_SETUP_2); insns.setImmutable(); bb = new BasicBlock(label, insns, IntList.makeImmutable(label2), label2); addBlock(bb, IntList.EMPTY); insns = new InsnList(isStatic() ? 2 : 1); if (isStatic()) { insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg), pos, synchReg, RegisterSpecList.EMPTY)); } insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos, RegisterSpecList.make(synchReg), StdTypeList.EMPTY); insns.set(isStatic() ? 1 :0, insn); insns.setImmutable(); bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0); addBlock(bb, IntList.EMPTY); } } /** * Constructs and adds the return block, if necessary. The return * block merely contains an appropriate {@code return} * instruction. */ private void addReturnBlock() { Rop returnOp = machine.getReturnOp(); if (returnOp == null) { /* * The method being converted never returns normally, so there's * no need for a return block. */ return; } SourcePosition returnPos = machine.getReturnPosition(); int label = getSpecialLabel(RETURN); if (isSynchronized()) { InsnList insns = new InsnList(1); Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos, RegisterSpecList.make(getSynchReg()), StdTypeList.EMPTY); insns.set(0, insn); insns.setImmutable(); int nextLabel = getSpecialLabel(SYNCH_RETURN); BasicBlock bb = new BasicBlock(label, insns, IntList.makeImmutable(nextLabel), nextLabel); addBlock(bb, IntList.EMPTY); label = nextLabel; } InsnList insns = new InsnList(1); TypeList sourceTypes = returnOp.getSources(); RegisterSpecList sources; if (sourceTypes.size() == 0) { sources = RegisterSpecList.EMPTY; } else { RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0)); sources = RegisterSpecList.make(source); } Insn insn = new PlainInsn(returnOp, returnPos, null, sources); insns.set(0, insn); insns.setImmutable(); BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1); addBlock(bb, IntList.EMPTY); } /** * Constructs and adds, if necessary, the catch-all exception handler * block to deal with unwinding the lock taken on entry to a synchronized * method. */ private void addSynchExceptionHandlerBlock() { if (!synchNeedsExceptionHandler) { /* * The method being converted either isn't synchronized or * can't possibly throw exceptions in its main body, so * there's no need for a synchronized method exception * handler. */ return; } SourcePosition pos = method.makeSourcePosistion(0); RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE); BasicBlock bb; Insn insn; InsnList insns = new InsnList(2); insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos, exReg, RegisterSpecList.EMPTY); insns.set(0, insn); insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos, RegisterSpecList.make(getSynchReg()), StdTypeList.EMPTY); insns.set(1, insn); insns.setImmutable(); int label2 = getSpecialLabel(SYNCH_CATCH_2); bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns, IntList.makeImmutable(label2), label2); addBlock(bb, IntList.EMPTY); insns = new InsnList(1); insn = new ThrowingInsn(Rops.THROW, pos, RegisterSpecList.make(exReg), StdTypeList.EMPTY); insns.set(0, insn); insns.setImmutable(); bb = new BasicBlock(label2, insns, IntList.EMPTY, -1); addBlock(bb, IntList.EMPTY); } /** * Creates the exception handler setup blocks. "maxLocals" * below is because that's the register number corresponding * to the sole element on a one-deep stack (which is the * situation at the start of an exception handler block). */ private void addExceptionSetupBlocks() { int len = catchInfos.length; for (int i = 0; i < len; i++) { CatchInfo catches = catchInfos[i]; if (catches != null) { for (ExceptionHandlerSetup one : catches.getSetups()) { Insn proto = labelToBlock(i).getFirstInsn(); SourcePosition pos = proto.getPosition(); InsnList il = new InsnList(2); Insn insn = new PlainInsn(Rops.opMoveException(one.getCaughtType()), pos, RegisterSpec.make(maxLocals, one.getCaughtType()), RegisterSpecList.EMPTY); il.set(0, insn); insn = new PlainInsn(Rops.GOTO, pos, null, RegisterSpecList.EMPTY); il.set(1, insn); il.setImmutable(); BasicBlock bb = new BasicBlock(one.getLabel(), il, IntList.makeImmutable(i), i); addBlock(bb, startFrames[i].getSubroutines()); } } } } /** * Checks to see if the basic block is a subroutine caller block. * * @param bb {@code non-null;} the basic block in question * @return true if this block calls a subroutine */ private boolean isSubroutineCaller(BasicBlock bb) { IntList successors = bb.getSuccessors(); if (successors.size() < 2) return false; int subLabel = successors.get(1); return (subLabel < subroutines.length) && (subroutines[subLabel] != null); } /** * Inlines any subroutine calls. */ private void inlineSubroutines() { final IntList reachableSubroutineCallerLabels = new IntList(4); /* * Compile a list of all subroutine calls reachable * through the normal (non-subroutine) flow. We do this first, since * we'll be affecting the call flow as we go. * * Start at label 0 -- the param assignment block has nothing for us */ forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() { public void visitBlock(BasicBlock b) { if (isSubroutineCaller(b)) { reachableSubroutineCallerLabels.add(b.getLabel()); } } }); /* * Convert the resultSubroutines list, indexed by block index, * to a label-to-subroutines mapping used by the inliner. */ int largestAllocedLabel = getAvailableLabel(); ArrayList labelToSubroutines = new ArrayList(largestAllocedLabel); for (int i = 0; i < largestAllocedLabel; i++) { labelToSubroutines.add(null); } for (int i = 0; i < result.size(); i++) { BasicBlock b = result.get(i); if (b == null) { continue; } IntList subroutineList = resultSubroutines.get(i); labelToSubroutines.set(b.getLabel(), subroutineList); } /* * Inline all reachable subroutines. * Inner subroutines will be inlined as they are encountered. */ int sz = reachableSubroutineCallerLabels.size(); for (int i = 0 ; i < sz ; i++) { int label = reachableSubroutineCallerLabels.get(i); new SubroutineInliner( new LabelAllocator(getAvailableLabel()), labelToSubroutines) .inlineSubroutineCalledFrom(labelToBlock(label)); } // Now find the blocks that aren't reachable and remove them deleteUnreachableBlocks(); } /** * Deletes all blocks that cannot be reached. This is run to delete * original subroutine blocks after subroutine inlining. */ private void deleteUnreachableBlocks() { final IntList reachableLabels = new IntList(result.size()); // subroutine inlining is done now and we won't update this list here resultSubroutines.clear(); forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT), new BasicBlock.Visitor() { public void visitBlock(BasicBlock b) { reachableLabels.add(b.getLabel()); } }); reachableLabels.sort(); for (int i = result.size() - 1 ; i >= 0 ; i--) { if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) { result.remove(i); // unnecessary here really, since subroutine inlining is done //resultSubroutines.remove(i); } } } /** * Allocates labels, without requiring previously allocated labels * to have been added to the blocks list. */ private static class LabelAllocator { int nextAvailableLabel; /** * @param startLabel available label to start allocating from */ LabelAllocator(int startLabel) { nextAvailableLabel = startLabel; } /** * @return next available label */ int getNextLabel() { return nextAvailableLabel++; } } /** * Allocates labels for exception setup blocks. */ private class ExceptionSetupLabelAllocator extends LabelAllocator { int maxSetupLabel; ExceptionSetupLabelAllocator() { super(maxLabel); maxSetupLabel = maxLabel + method.getCatches().size(); } @Override int getNextLabel() { if (nextAvailableLabel >= maxSetupLabel) { throw new IndexOutOfBoundsException(); } return nextAvailableLabel ++; } } /** * Inlines a subroutine. Start by calling * {@link #inlineSubroutineCalledFrom}. */ private class SubroutineInliner { /** * maps original label to the label that will be used by the * inlined version */ private final HashMap origLabelToCopiedLabel; /** set of original labels that need to be copied */ private final BitSet workList; /** the label of the original start block for this subroutine */ private int subroutineStart; /** the label of the ultimate return block */ private int subroutineSuccessor; /** used for generating new labels for copied blocks */ private final LabelAllocator labelAllocator; /** * A mapping, indexed by label, to subroutine nesting list. * The subroutine nest list is as returned by * {@link Frame#getSubroutines}. */ private final ArrayList labelToSubroutines; SubroutineInliner(final LabelAllocator labelAllocator, ArrayList labelToSubroutines) { origLabelToCopiedLabel = new HashMap(); workList = new BitSet(maxLabel); this.labelAllocator = labelAllocator; this.labelToSubroutines = labelToSubroutines; } /** * Inlines a subroutine. * * @param b block where {@code jsr} occurred in the original bytecode */ void inlineSubroutineCalledFrom(final BasicBlock b) { /* * The 0th successor of a subroutine caller block is where * the subroutine should return to. The 1st successor is * the start block of the subroutine. */ subroutineSuccessor = b.getSuccessors().get(0); subroutineStart = b.getSuccessors().get(1); /* * This allocates an initial label and adds the first * block to the worklist. */ int newSubStartLabel = mapOrAllocateLabel(subroutineStart); for (int label = workList.nextSetBit(0); label >= 0; label = workList.nextSetBit(0)) { workList.clear(label); int newLabel = origLabelToCopiedLabel.get(label); copyBlock(label, newLabel); if (isSubroutineCaller(labelToBlock(label))) { new SubroutineInliner(labelAllocator, labelToSubroutines) .inlineSubroutineCalledFrom(labelToBlock(newLabel)); } } /* * Replace the original caller block, since we now have a * new successor */ addOrReplaceBlockNoDelete( new BasicBlock(b.getLabel(), b.getInsns(), IntList.makeImmutable (newSubStartLabel), newSubStartLabel), labelToSubroutines.get(b.getLabel())); } /** * Copies a basic block, mapping its successors along the way. * * @param origLabel original block label * @param newLabel label that the new block should have */ private void copyBlock(int origLabel, int newLabel) { BasicBlock origBlock = labelToBlock(origLabel); final IntList origSuccessors = origBlock.getSuccessors(); IntList successors; int primarySuccessor = -1; Subroutine subroutine; if (isSubroutineCaller(origBlock)) { /* * A subroutine call inside a subroutine call. * Set up so we can recurse. The caller block should have * it's first successor be a copied block that will be * the subroutine's return point. It's second successor will * be copied when we recurse, and remains as the original * label of the start of the inner subroutine. */ successors = IntList.makeImmutable( mapOrAllocateLabel(origSuccessors.get(0)), origSuccessors.get(1)); // primary successor will be set when this block is replaced } else if (null != (subroutine = subroutineFromRetBlock(origLabel))) { /* * this is a ret block -- its successor * should be subroutineSuccessor */ // Sanity check if (subroutine.startBlock != subroutineStart) { throw new RuntimeException ( "ret instruction returns to label " + Hex.u2 (subroutine.startBlock) + " expected: " + Hex.u2(subroutineStart)); } successors = IntList.makeImmutable(subroutineSuccessor); primarySuccessor = subroutineSuccessor; } else { // Map all the successor labels int origPrimary = origBlock.getPrimarySuccessor(); int sz = origSuccessors.size(); successors = new IntList(sz); for (int i = 0 ; i < sz ; i++) { int origSuccLabel = origSuccessors.get(i); int newSuccLabel = mapOrAllocateLabel(origSuccLabel); successors.add(newSuccLabel); if (origPrimary == origSuccLabel) { primarySuccessor = newSuccLabel; } } successors.setImmutable(); } addBlock ( new BasicBlock(newLabel, filterMoveReturnAddressInsns(origBlock.getInsns()), successors, primarySuccessor), labelToSubroutines.get(newLabel)); } /** * Checks to see if a specified label is involved in a specified * subroutine. * * @param label {@code >= 0;} a basic block label * @param subroutineStart {@code >= 0;} a subroutine as identified * by the label of its start block * @return true if the block is dominated by the subroutine call */ private boolean involvedInSubroutine(int label, int subroutineStart) { IntList subroutinesList = labelToSubroutines.get(label); return (subroutinesList != null && subroutinesList.size() > 0 && subroutinesList.top() == subroutineStart); } /** * Maps the label of a pre-copied block to the label of the inlined * block, allocating a new label and adding it to the worklist * if necessary. If the origLabel is a "special" label, it * is returned exactly and not scheduled for duplication: copying * never proceeds past a special label, which likely is the function * return block or an immediate predecessor. * * @param origLabel label of original, pre-copied block * @return label for new, inlined block */ private int mapOrAllocateLabel(int origLabel) { int resultLabel; Integer mappedLabel = origLabelToCopiedLabel.get(origLabel); if (mappedLabel != null) { resultLabel = mappedLabel; } else if (!involvedInSubroutine(origLabel,subroutineStart)) { /* * A subroutine has ended by some means other than a "ret" * (which really means a throw caught later). */ resultLabel = origLabel; } else { resultLabel = labelAllocator.getNextLabel(); workList.set(origLabel); origLabelToCopiedLabel.put(origLabel, resultLabel); // The new label has the same frame as the original label while (labelToSubroutines.size() <= resultLabel) { labelToSubroutines.add(null); } labelToSubroutines.set(resultLabel, labelToSubroutines.get(origLabel)); } return resultLabel; } } /** * Finds a {@code Subroutine} that is returned from by a {@code ret} in * a given block. * * @param label A block that originally contained a {@code ret} instruction * @return {@code null-ok;} found subroutine or {@code null} if none * was found */ private Subroutine subroutineFromRetBlock(int label) { for (int i = subroutines.length - 1 ; i >= 0 ; i--) { if (subroutines[i] != null) { Subroutine subroutine = subroutines[i]; if (subroutine.retBlocks.get(label)) { return subroutine; } } } return null; } /** * Removes all {@code move-return-address} instructions, returning a new * {@code InsnList} if necessary. The {@code move-return-address} * insns are dead code after subroutines have been inlined. * * @param insns {@code InsnList} that may contain * {@code move-return-address} insns * @return {@code InsnList} with {@code move-return-address} removed */ private InsnList filterMoveReturnAddressInsns(InsnList insns) { int sz; int newSz = 0; // First see if we need to filter, and if so what the new size will be sz = insns.size(); for (int i = 0; i < sz; i++) { if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) { newSz++; } } if (newSz == sz) { return insns; } // Make a new list without the MOVE_RETURN_ADDRESS insns InsnList newInsns = new InsnList(newSz); int newIndex = 0; for (int i = 0; i < sz; i++) { Insn insn = insns.get(i); if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) { newInsns.set(newIndex++, insn); } } newInsns.setImmutable(); return newInsns; } /** * Visits each non-subroutine block once in depth-first successor order. * * @param firstLabel label of start block * @param v callback interface */ private void forEachNonSubBlockDepthFirst(int firstLabel, BasicBlock.Visitor v) { forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel), v, new BitSet(maxLabel)); } /** * Visits each block once in depth-first successor order, ignoring * {@code jsr} targets. Worker for {@link #forEachNonSubBlockDepthFirst}. * * @param next next block to visit * @param v callback interface * @param visited set of blocks already visited */ private void forEachNonSubBlockDepthFirst0( BasicBlock next, BasicBlock.Visitor v, BitSet visited) { v.visitBlock(next); visited.set(next.getLabel()); IntList successors = next.getSuccessors(); int sz = successors.size(); for (int i = 0; i < sz; i++) { int succ = successors.get(i); if (visited.get(succ)) { continue; } if (isSubroutineCaller(next) && i > 0) { // ignore jsr targets continue; } /* * Ignore missing labels: they're successors of * subroutines that never invoke a ret. */ int idx = labelToResultIndex(succ); if (idx >= 0) { forEachNonSubBlockDepthFirst0(result.get(idx), v, visited); } } } }