Home | History | Annotate | Download | only in code
      1 /*
      2  * Copyright (C) 2007 The Android Open Source Project
      3  *
      4  * Licensed under the Apache License, Version 2.0 (the "License");
      5  * you may not use this file except in compliance with the License.
      6  * You may obtain a copy of the License at
      7  *
      8  *      http://www.apache.org/licenses/LICENSE-2.0
      9  *
     10  * Unless required by applicable law or agreed to in writing, software
     11  * distributed under the License is distributed on an "AS IS" BASIS,
     12  * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
     13  * See the License for the specific language governing permissions and
     14  * limitations under the License.
     15  */
     16 
     17 package com.android.dx.cf.code;
     18 
     19 import com.android.dx.rop.code.AccessFlags;
     20 import com.android.dx.rop.code.BasicBlock;
     21 import com.android.dx.rop.code.BasicBlockList;
     22 import com.android.dx.rop.code.Insn;
     23 import com.android.dx.rop.code.InsnList;
     24 import com.android.dx.rop.code.PlainCstInsn;
     25 import com.android.dx.rop.code.PlainInsn;
     26 import com.android.dx.rop.code.RegisterSpec;
     27 import com.android.dx.rop.code.RegisterSpecList;
     28 import com.android.dx.rop.code.Rop;
     29 import com.android.dx.rop.code.RopMethod;
     30 import com.android.dx.rop.code.Rops;
     31 import com.android.dx.rop.code.SourcePosition;
     32 import com.android.dx.rop.code.ThrowingCstInsn;
     33 import com.android.dx.rop.code.ThrowingInsn;
     34 import com.android.dx.rop.code.TranslationAdvice;
     35 import com.android.dx.rop.cst.CstInteger;
     36 import com.android.dx.rop.cst.CstType;
     37 import com.android.dx.rop.type.Prototype;
     38 import com.android.dx.rop.type.StdTypeList;
     39 import com.android.dx.rop.type.Type;
     40 import com.android.dx.rop.type.TypeList;
     41 import com.android.dx.util.Bits;
     42 import com.android.dx.util.Hex;
     43 import com.android.dx.util.IntList;
     44 import java.util.ArrayList;
     45 import java.util.BitSet;
     46 import java.util.HashMap;
     47 
     48 /**
     49  * Utility that converts a basic block list into a list of register-oriented
     50  * blocks.
     51  */
     52 public final class Ropper {
     53     /** label offset for the parameter assignment block */
     54     private static final int PARAM_ASSIGNMENT = -1;
     55 
     56     /** label offset for the return block */
     57     private static final int RETURN = -2;
     58 
     59     /** label offset for the synchronized method final return block */
     60     private static final int SYNCH_RETURN = -3;
     61 
     62     /** label offset for the first synchronized method setup block */
     63     private static final int SYNCH_SETUP_1 = -4;
     64 
     65     /** label offset for the second synchronized method setup block */
     66     private static final int SYNCH_SETUP_2 = -5;
     67 
     68     /**
     69      * label offset for the first synchronized method exception
     70      * handler block
     71      */
     72     private static final int SYNCH_CATCH_1 = -6;
     73 
     74     /**
     75      * label offset for the second synchronized method exception
     76      * handler block
     77      */
     78     private static final int SYNCH_CATCH_2 = -7;
     79 
     80     /** number of special label offsets */
     81     private static final int SPECIAL_LABEL_COUNT = 7;
     82 
     83     /** {@code non-null;} method being converted */
     84     private final ConcreteMethod method;
     85 
     86     /** {@code non-null;} original block list */
     87     private final ByteBlockList blocks;
     88 
     89     /** max locals of the method */
     90     private final int maxLocals;
     91 
     92     /** max label (exclusive) of any original bytecode block */
     93     private final int maxLabel;
     94 
     95     /** {@code non-null;} simulation machine to use */
     96     private final RopperMachine machine;
     97 
     98     /** {@code non-null;} simulator to use */
     99     private final Simulator sim;
    100 
    101     /**
    102      * {@code non-null;} sparse array mapping block labels to initial frame
    103      * contents, if known
    104      */
    105     private final Frame[] startFrames;
    106 
    107     /** {@code non-null;} output block list in-progress */
    108     private final ArrayList<BasicBlock> result;
    109 
    110     /**
    111      * {@code non-null;} list of subroutine-nest labels
    112      * (See {@link Frame#getSubroutines} associated with each result block.
    113      * Parallel to {@link Ropper#result}.
    114      */
    115     private final ArrayList<IntList> resultSubroutines;
    116 
    117     /**
    118      * {@code non-null;} for each block (by label) that is used as an exception
    119      * handler, the type of exception it catches
    120      */
    121     private final Type[] catchTypes;
    122 
    123     /**
    124      * whether an exception-handler block for a synchronized method was
    125      * ever required
    126      */
    127     private boolean synchNeedsExceptionHandler;
    128 
    129     /**
    130      * {@code non-null;} list of subroutines indexed by label of start
    131      * address */
    132     private final Subroutine[] subroutines;
    133 
    134     /** true if {@code subroutines} is non-empty */
    135     private boolean hasSubroutines;
    136 
    137     /**
    138      * Keeps track of subroutines that exist in java form and are inlined in
    139      * Rop form.
    140      */
    141     private class Subroutine {
    142         /** list of all blocks that jsr to this subroutine */
    143         private BitSet callerBlocks;
    144         /** List of all blocks that return from this subroutine */
    145         private BitSet retBlocks;
    146         /** first block in this subroutine */
    147         private int startBlock;
    148 
    149         /**
    150          * Constructs instance.
    151          *
    152          * @param startBlock First block of the subroutine.
    153          */
    154         Subroutine(int startBlock) {
    155             this.startBlock = startBlock;
    156             retBlocks = new BitSet(maxLabel);
    157             callerBlocks = new BitSet(maxLabel);
    158             hasSubroutines = true;
    159         }
    160 
    161         /**
    162          * Constructs instance.
    163          *
    164          * @param startBlock First block of the subroutine.
    165          * @param retBlock one of the ret blocks (final blocks) of this
    166          * subroutine.
    167          */
    168         Subroutine(int startBlock, int retBlock) {
    169             this(startBlock);
    170             addRetBlock(retBlock);
    171         }
    172 
    173         /**
    174          * @return {@code >= 0;} the label of the subroutine's start block.
    175          */
    176         int getStartBlock() {
    177             return startBlock;
    178         }
    179 
    180         /**
    181          * Adds a label to the list of ret blocks (final blocks) for this
    182          * subroutine.
    183          *
    184          * @param retBlock ret block label
    185          */
    186         void addRetBlock(int retBlock) {
    187             retBlocks.set(retBlock);
    188         }
    189 
    190         /**
    191          * Adds a label to the list of caller blocks for this subroutine.
    192          *
    193          * @param label a block that invokes this subroutine.
    194          */
    195         void addCallerBlock(int label) {
    196             callerBlocks.set(label);
    197         }
    198 
    199         /**
    200          * Generates a list of subroutine successors. Note: successor blocks
    201          * could be listed more than once. This is ok, because this successor
    202          * list (and the block it's associated with) will be copied and inlined
    203          * before we leave the ropper. Redundent successors will result in
    204          * redundent (no-op) merges.
    205          *
    206          * @return all currently known successors
    207          * (return destinations) for that subroutine
    208          */
    209         IntList getSuccessors() {
    210             IntList successors = new IntList(callerBlocks.size());
    211 
    212             /*
    213              * For each subroutine caller, get it's target. If the
    214              * target is us, add the ret target (subroutine successor)
    215              * to our list
    216              */
    217 
    218             for (int label = callerBlocks.nextSetBit(0); label >= 0;
    219                  label = callerBlocks.nextSetBit(label+1)) {
    220                 BasicBlock subCaller = labelToBlock(label);
    221                 successors.add(subCaller.getSuccessors().get(0));
    222             }
    223 
    224             successors.setImmutable();
    225 
    226             return successors;
    227         }
    228 
    229         /**
    230          * Merges the specified frame into this subroutine's successors,
    231          * setting {@code workSet} as appropriate. To be called with
    232          * the frame of a subroutine ret block.
    233          *
    234          * @param frame {@code non-null;} frame from ret block to merge
    235          * @param workSet {@code non-null;} workset to update
    236          */
    237         void mergeToSuccessors(Frame frame, int[] workSet) {
    238             for (int label = callerBlocks.nextSetBit(0); label >= 0;
    239                  label = callerBlocks.nextSetBit(label+1)) {
    240                 BasicBlock subCaller = labelToBlock(label);
    241                 int succLabel = subCaller.getSuccessors().get(0);
    242 
    243                 Frame subFrame = frame.subFrameForLabel(startBlock, label);
    244 
    245                 if (subFrame != null) {
    246                     mergeAndWorkAsNecessary(succLabel, -1, null,
    247                             subFrame, workSet);
    248                 } else {
    249                     Bits.set(workSet, label);
    250                 }
    251             }
    252         }
    253     }
    254 
    255     /**
    256      * Converts a {@link ConcreteMethod} to a {@link RopMethod}.
    257      *
    258      * @param method {@code non-null;} method to convert
    259      * @param advice {@code non-null;} translation advice to use
    260      * @return {@code non-null;} the converted instance
    261      */
    262     public static RopMethod convert(ConcreteMethod method,
    263             TranslationAdvice advice) {
    264         try {
    265             Ropper r = new Ropper(method, advice);
    266             r.doit();
    267             return r.getRopMethod();
    268         } catch (SimException ex) {
    269             ex.addContext("...while working on method " +
    270                           method.getNat().toHuman());
    271             throw ex;
    272         }
    273     }
    274 
    275     /**
    276      * Constructs an instance. This class is not publicly instantiable; use
    277      * {@link #convert}.
    278      *
    279      * @param method {@code non-null;} method to convert
    280      * @param advice {@code non-null;} translation advice to use
    281      */
    282     private Ropper(ConcreteMethod method, TranslationAdvice advice) {
    283         if (method == null) {
    284             throw new NullPointerException("method == null");
    285         }
    286 
    287         if (advice == null) {
    288             throw new NullPointerException("advice == null");
    289         }
    290 
    291         this.method = method;
    292         this.blocks = BasicBlocker.identifyBlocks(method);
    293         this.maxLabel = blocks.getMaxLabel();
    294         this.maxLocals = method.getMaxLocals();
    295         this.machine = new RopperMachine(this, method, advice);
    296         this.sim = new Simulator(machine, method);
    297         this.startFrames = new Frame[maxLabel];
    298         this.subroutines = new Subroutine[maxLabel];
    299 
    300         /*
    301          * The "* 2 + 10" below is to conservatively believe that every
    302          * block is an exception handler target and should also
    303          * take care of enough other possible extra overhead such that
    304          * the underlying array is unlikely to need resizing.
    305          */
    306         this.result = new ArrayList<BasicBlock>(blocks.size() * 2 + 10);
    307         this.resultSubroutines =
    308             new ArrayList<IntList>(blocks.size() * 2 + 10);
    309 
    310         this.catchTypes = new Type[maxLabel];
    311         this.synchNeedsExceptionHandler = false;
    312 
    313         /*
    314          * Set up the first stack frame with the right limits, but leave it
    315          * empty here (to be filled in outside of the constructor).
    316          */
    317         startFrames[0] = new Frame(maxLocals, method.getMaxStack());
    318     }
    319 
    320     /**
    321      * Gets the first (lowest) register number to use as the temporary
    322      * area when unwinding stack manipulation ops.
    323      *
    324      * @return {@code >= 0;} the first register to use
    325      */
    326     /*package*/ int getFirstTempStackReg() {
    327         /*
    328          * We use the register that is just past the deepest possible
    329          * stack element, plus one if the method is synchronized to
    330          * avoid overlapping with the synch register. We don't need to
    331          * do anything else special at this level, since later passes
    332          * will merely notice the highest register used by explicit
    333          * inspection.
    334          */
    335         int regCount = getNormalRegCount();
    336         return isSynchronized() ? regCount + 1 : regCount;
    337     }
    338 
    339     /**
    340      * Gets the label for the exception handler setup block corresponding
    341      * to the given label.
    342      *
    343      * @param label {@code >= 0;} the original label
    344      * @return {@code >= 0;} the corresponding exception handler setup label
    345      */
    346     private int getExceptionSetupLabel(int label) {
    347         return maxLabel + label;
    348     }
    349 
    350     /**
    351      * Gets the label for the given special-purpose block. The given label
    352      * should be one of the static constants defined by this class.
    353      *
    354      * @param label {@code < 0;} the special label constant
    355      * @return {@code >= 0;} the actual label value to use
    356      */
    357     private int getSpecialLabel(int label) {
    358         /*
    359          * The label is bitwise-complemented so that mistakes where
    360          * LABEL is used instead of getSpecialLabel(LABEL) cause a
    361          * failure at block construction time, since negative labels
    362          * are illegal. We multiply maxLabel by 2 since 0..maxLabel
    363          * (exclusive) are the original blocks and
    364          * maxLabel..(maxLabel*2) are reserved for exception handler
    365          * setup blocks (see getExceptionSetupLabel(), above).
    366          */
    367         return (maxLabel * 2) + ~label;
    368     }
    369 
    370     /**
    371      * Gets the minimum label for unreserved use.
    372      *
    373      * @return {@code >= 0;} the minimum label
    374      */
    375     private int getMinimumUnreservedLabel() {
    376         /*
    377          * The labels below ((maxLabel * 2) + SPECIAL_LABEL_COUNT) are
    378          * reserved for particular uses.
    379          */
    380 
    381         return (maxLabel * 2) + SPECIAL_LABEL_COUNT;
    382     }
    383 
    384     /**
    385      * Gets an arbitrary unreserved and available label.
    386      *
    387      * @return {@code >= 0;} the label
    388      */
    389     private int getAvailableLabel() {
    390         int candidate = getMinimumUnreservedLabel();
    391 
    392         for (BasicBlock bb : result) {
    393             int label = bb.getLabel();
    394             if (label >= candidate) {
    395                 candidate = label + 1;
    396             }
    397         }
    398 
    399         return candidate;
    400     }
    401 
    402     /**
    403      * Gets whether the method being translated is synchronized.
    404      *
    405      * @return whether the method being translated is synchronized
    406      */
    407     private boolean isSynchronized() {
    408         int accessFlags = method.getAccessFlags();
    409         return (accessFlags & AccessFlags.ACC_SYNCHRONIZED) != 0;
    410     }
    411 
    412     /**
    413      * Gets whether the method being translated is static.
    414      *
    415      * @return whether the method being translated is static
    416      */
    417     private boolean isStatic() {
    418         int accessFlags = method.getAccessFlags();
    419         return (accessFlags & AccessFlags.ACC_STATIC) != 0;
    420     }
    421 
    422     /**
    423      * Gets the total number of registers used for "normal" purposes (i.e.,
    424      * for the straightforward translation from the original Java).
    425      *
    426      * @return {@code >= 0;} the total number of registers used
    427      */
    428     private int getNormalRegCount() {
    429         return maxLocals + method.getMaxStack();
    430     }
    431 
    432     /**
    433      * Gets the register spec to use to hold the object to synchronize on,
    434      * for a synchronized method.
    435      *
    436      * @return {@code non-null;} the register spec
    437      */
    438     private RegisterSpec getSynchReg() {
    439         /*
    440          * We use the register that is just past the deepest possible
    441          * stack element, with a minimum of v1 since v0 is what's
    442          * always used to hold the caught exception when unwinding. We
    443          * don't need to do anything else special at this level, since
    444          * later passes will merely notice the highest register used
    445          * by explicit inspection.
    446          */
    447         int reg = getNormalRegCount();
    448         return RegisterSpec.make((reg < 1) ? 1 : reg, Type.OBJECT);
    449     }
    450 
    451     /**
    452      * Searches {@link #result} for a block with the given label. Returns its
    453      * index if found, or returns {@code -1} if there is no such block.
    454      *
    455      * @param label the label to look for
    456      * @return {@code >= -1;} the index for the block with the given label or
    457      * {@code -1} if there is no such block
    458      */
    459     private int labelToResultIndex(int label) {
    460         int sz = result.size();
    461         for (int i = 0; i < sz; i++) {
    462             BasicBlock one = result.get(i);
    463             if (one.getLabel() == label) {
    464                 return i;
    465             }
    466         }
    467 
    468         return -1;
    469     }
    470 
    471     /**
    472      * Searches {@link #result} for a block with the given label. Returns it if
    473      * found, or throws an exception if there is no such block.
    474      *
    475      * @param label the label to look for
    476      * @return {@code non-null;} the block with the given label
    477      */
    478     private BasicBlock labelToBlock(int label) {
    479         int idx = labelToResultIndex(label);
    480 
    481         if (idx < 0) {
    482             throw new IllegalArgumentException("no such label " +
    483                     Hex.u2(label));
    484         }
    485 
    486         return result.get(idx);
    487     }
    488 
    489     /**
    490      * Adds a block to the output result.
    491      *
    492      * @param block {@code non-null;} the block to add
    493      * @param subroutines {@code non-null;} subroutine label list
    494      * as described in {@link Frame#getSubroutines}
    495      */
    496     private void addBlock(BasicBlock block, IntList subroutines) {
    497         if (block == null) {
    498             throw new NullPointerException("block == null");
    499         }
    500 
    501         result.add(block);
    502         subroutines.throwIfMutable();
    503         resultSubroutines.add(subroutines);
    504     }
    505 
    506     /**
    507      * Adds or replace a block in the output result. If this is a
    508      * replacement, then any extra blocks that got added with the
    509      * original get removed as a result of calling this method.
    510      *
    511      * @param block {@code non-null;} the block to add or replace
    512      * @param subroutines {@code non-null;} subroutine label list
    513      * as described in {@link Frame#getSubroutines}
    514      * @return {@code true} if the block was replaced or
    515      * {@code false} if it was added for the first time
    516      */
    517     private boolean addOrReplaceBlock(BasicBlock block, IntList subroutines) {
    518         if (block == null) {
    519             throw new NullPointerException("block == null");
    520         }
    521 
    522         int idx = labelToResultIndex(block.getLabel());
    523         boolean ret;
    524 
    525         if (idx < 0) {
    526             ret = false;
    527         } else {
    528             /*
    529              * We are replacing a pre-existing block, so find any
    530              * blocks that got added as part of the original and
    531              * remove those too. Such blocks are (possibly indirect)
    532              * successors of this block which are out of the range of
    533              * normally-translated blocks.
    534              */
    535             removeBlockAndSpecialSuccessors(idx);
    536             ret = true;
    537         }
    538 
    539         result.add(block);
    540         subroutines.throwIfMutable();
    541         resultSubroutines.add(subroutines);
    542         return ret;
    543     }
    544 
    545     /**
    546      * Adds or replaces a block in the output result. Do not delete
    547      * any successors.
    548      *
    549      * @param block {@code non-null;} the block to add or replace
    550      * @param subroutines {@code non-null;} subroutine label list
    551      * as described in {@link Frame#getSubroutines}
    552      * @return {@code true} if the block was replaced or
    553      * {@code false} if it was added for the first time
    554      */
    555     private boolean addOrReplaceBlockNoDelete(BasicBlock block,
    556             IntList subroutines) {
    557         if (block == null) {
    558             throw new NullPointerException("block == null");
    559         }
    560 
    561         int idx = labelToResultIndex(block.getLabel());
    562         boolean ret;
    563 
    564         if (idx < 0) {
    565             ret = false;
    566         } else {
    567             result.remove(idx);
    568             resultSubroutines.remove(idx);
    569             ret = true;
    570         }
    571 
    572         result.add(block);
    573         subroutines.throwIfMutable();
    574         resultSubroutines.add(subroutines);
    575         return ret;
    576     }
    577 
    578     /**
    579      * Helper for {@link #addOrReplaceBlock} which recursively removes
    580      * the given block and all blocks that are (direct and indirect)
    581      * successors of it whose labels indicate that they are not in the
    582      * normally-translated range.
    583      *
    584      * @param idx {@code non-null;} block to remove (etc.)
    585      */
    586     private void removeBlockAndSpecialSuccessors(int idx) {
    587         int minLabel = getMinimumUnreservedLabel();
    588         BasicBlock block = result.get(idx);
    589         IntList successors = block.getSuccessors();
    590         int sz = successors.size();
    591 
    592         result.remove(idx);
    593         resultSubroutines.remove(idx);
    594 
    595         for (int i = 0; i < sz; i++) {
    596             int label = successors.get(i);
    597             if (label >= minLabel) {
    598                 idx = labelToResultIndex(label);
    599                 if (idx < 0) {
    600                     throw new RuntimeException("Invalid label "
    601                             + Hex.u2(label));
    602                 }
    603                 removeBlockAndSpecialSuccessors(idx);
    604             }
    605         }
    606     }
    607 
    608     /**
    609      * Extracts the resulting {@link RopMethod} from the instance.
    610      *
    611      * @return {@code non-null;} the method object
    612      */
    613     private RopMethod getRopMethod() {
    614 
    615         // Construct the final list of blocks.
    616 
    617         int sz = result.size();
    618         BasicBlockList bbl = new BasicBlockList(sz);
    619         for (int i = 0; i < sz; i++) {
    620             bbl.set(i, result.get(i));
    621         }
    622         bbl.setImmutable();
    623 
    624         // Construct the method object to wrap it all up.
    625 
    626         /*
    627          * Note: The parameter assignment block is always the first
    628          * that should be executed, hence the second argument to the
    629          * constructor.
    630          */
    631         return new RopMethod(bbl, getSpecialLabel(PARAM_ASSIGNMENT));
    632     }
    633 
    634     /**
    635      * Does the conversion.
    636      */
    637     private void doit() {
    638         int[] workSet = Bits.makeBitSet(maxLabel);
    639 
    640         Bits.set(workSet, 0);
    641         addSetupBlocks();
    642         setFirstFrame();
    643 
    644         for (;;) {
    645             int offset = Bits.findFirst(workSet, 0);
    646             if (offset < 0) {
    647                 break;
    648             }
    649             Bits.clear(workSet, offset);
    650             ByteBlock block = blocks.labelToBlock(offset);
    651             Frame frame = startFrames[offset];
    652             try {
    653                 processBlock(block, frame, workSet);
    654             } catch (SimException ex) {
    655                 ex.addContext("...while working on block " + Hex.u2(offset));
    656                 throw ex;
    657             }
    658         }
    659 
    660         addReturnBlock();
    661         addSynchExceptionHandlerBlock();
    662         addExceptionSetupBlocks();
    663 
    664         if (hasSubroutines) {
    665             // Subroutines are very rare, so skip this step if it's n/a
    666             inlineSubroutines();
    667         }
    668     }
    669 
    670     /**
    671      * Sets up the first frame to contain all the incoming parameters in
    672      * locals.
    673      */
    674     private void setFirstFrame() {
    675         Prototype desc = method.getEffectiveDescriptor();
    676         startFrames[0].initializeWithParameters(desc.getParameterTypes());
    677         startFrames[0].setImmutable();
    678     }
    679 
    680     /**
    681      * Processes the given block.
    682      *
    683      * @param block {@code non-null;} block to process
    684      * @param frame {@code non-null;} start frame for the block
    685      * @param workSet {@code non-null;} bits representing work to do,
    686      * which this method may add to
    687      */
    688     private void processBlock(ByteBlock block, Frame frame, int[] workSet) {
    689         // Prepare the list of caught exceptions for this block.
    690         ByteCatchList catches = block.getCatches();
    691         machine.startBlock(catches.toRopCatchList());
    692 
    693         /*
    694          * Using a copy of the given frame, simulate each instruction,
    695          * calling into machine for each.
    696          */
    697         frame = frame.copy();
    698         sim.simulate(block, frame);
    699         frame.setImmutable();
    700 
    701         int extraBlockCount = machine.getExtraBlockCount();
    702         ArrayList<Insn> insns = machine.getInsns();
    703         int insnSz = insns.size();
    704 
    705         /*
    706          * Merge the frame into each possible non-exceptional
    707          * successor.
    708          */
    709 
    710         int catchSz = catches.size();
    711         IntList successors = block.getSuccessors();
    712 
    713         int startSuccessorIndex;
    714 
    715         Subroutine calledSubroutine = null;
    716         if (machine.hasJsr()) {
    717             /*
    718              * If this frame ends in a JSR, only merge our frame with
    719              * the subroutine start, not the subroutine's return target.
    720              */
    721             startSuccessorIndex = 1;
    722 
    723             int subroutineLabel = successors.get(1);
    724 
    725             if (subroutines[subroutineLabel] == null) {
    726                 subroutines[subroutineLabel] =
    727                     new Subroutine (subroutineLabel);
    728             }
    729 
    730             subroutines[subroutineLabel].addCallerBlock(block.getLabel());
    731 
    732             calledSubroutine = subroutines[subroutineLabel];
    733         } else if (machine.hasRet()) {
    734             /*
    735              * This block ends in a ret, which means it's the final block
    736              * in some subroutine. Ultimately, this block will be copied
    737              * and inlined for each call and then disposed of.
    738              */
    739 
    740             ReturnAddress ra = machine.getReturnAddress();
    741             int subroutineLabel = ra.getSubroutineAddress();
    742 
    743             if (subroutines[subroutineLabel] == null) {
    744                 subroutines[subroutineLabel]
    745                         = new Subroutine (subroutineLabel, block.getLabel());
    746             } else {
    747                 subroutines[subroutineLabel].addRetBlock(block.getLabel());
    748             }
    749 
    750             successors = subroutines[subroutineLabel].getSuccessors();
    751             subroutines[subroutineLabel]
    752                     .mergeToSuccessors(frame, workSet);
    753             // Skip processing below since we just did it.
    754             startSuccessorIndex = successors.size();
    755         } else if (machine.wereCatchesUsed()) {
    756             /*
    757              * If there are catches, then the first successors
    758              * (which will either be all of them or all but the last one)
    759              * are catch targets.
    760              */
    761             startSuccessorIndex = catchSz;
    762         } else {
    763             startSuccessorIndex = 0;
    764         }
    765 
    766         int succSz = successors.size();
    767         for (int i = startSuccessorIndex; i < succSz;
    768              i++) {
    769             int succ = successors.get(i);
    770             try {
    771                 mergeAndWorkAsNecessary(succ, block.getLabel(),
    772                         calledSubroutine, frame, workSet);
    773             } catch (SimException ex) {
    774                 ex.addContext("...while merging to block " + Hex.u2(succ));
    775                 throw ex;
    776             }
    777         }
    778 
    779         if ((succSz == 0) && machine.returns()) {
    780             /*
    781              * The block originally contained a return, but it has
    782              * been made to instead end with a goto, and we need to
    783              * tell it at this point that its sole successor is the
    784              * return block. This has to happen after the merge loop
    785              * above, since, at this point, the return block doesn't
    786              * actually exist; it gets synthesized at the end of
    787              * processing the original blocks.
    788              */
    789             successors = IntList.makeImmutable(getSpecialLabel(RETURN));
    790             succSz = 1;
    791         }
    792 
    793         int primarySucc;
    794 
    795         if (succSz == 0) {
    796             primarySucc = -1;
    797         } else {
    798             primarySucc = machine.getPrimarySuccessorIndex();
    799             if (primarySucc >= 0) {
    800                 primarySucc = successors.get(primarySucc);
    801             }
    802         }
    803 
    804         /*
    805          * This variable is true only when the method is synchronized and
    806          * the block being processed can possibly throw an exception.
    807          */
    808         boolean synch = isSynchronized() && machine.canThrow();
    809 
    810         if (synch || (catchSz != 0)) {
    811             /*
    812              * Deal with exception handlers: Merge an exception-catch
    813              * frame into each possible exception handler, and
    814              * construct a new set of successors to point at the
    815              * exception handler setup blocks (which get synthesized
    816              * at the very end of processing).
    817              */
    818             boolean catchesAny = false;
    819             IntList newSucc = new IntList(succSz);
    820             for (int i = 0; i < catchSz; i++) {
    821                 ByteCatchList.Item one = catches.get(i);
    822                 CstType exceptionClass = one.getExceptionClass();
    823                 int targ = one.getHandlerPc();
    824 
    825                 catchesAny |= (exceptionClass == CstType.OBJECT);
    826 
    827                 Frame f = frame.makeExceptionHandlerStartFrame(exceptionClass);
    828 
    829                 try {
    830                     mergeAndWorkAsNecessary(targ, block.getLabel(),
    831                             null, f, workSet);
    832                 } catch (SimException ex) {
    833                     ex.addContext("...while merging exception to block " +
    834                                   Hex.u2(targ));
    835                     throw ex;
    836                 }
    837 
    838                 /*
    839                  * Set up the exception handler type, by setting it if
    840                  * the given handler has yet to be encountered, or by
    841                  * conservatively unioning if it has.
    842                  */
    843                 Type already = catchTypes[targ];
    844                 if (already == null) {
    845                     catchTypes[targ] = exceptionClass.getClassType();
    846                 } else if (already != exceptionClass.getClassType()) {
    847                     catchTypes[targ] = Type.OBJECT;
    848                 }
    849 
    850                 /*
    851                  * The synthesized exception setup block will have the
    852                  * label getExceptionSetupLabel(targ).
    853                  */
    854                 newSucc.add(getExceptionSetupLabel(targ));
    855             }
    856 
    857             if (synch && !catchesAny) {
    858                 /*
    859                  * The method is synchronized and this block doesn't
    860                  * already have a catch-all handler, so add one to the
    861                  * end, both in the successors and in the throwing
    862                  * instruction(s) at the end of the block (which is where
    863                  * the caught classes live).
    864                  */
    865                 newSucc.add(getSpecialLabel(SYNCH_CATCH_1));
    866                 synchNeedsExceptionHandler = true;
    867 
    868                 for (int i = insnSz - extraBlockCount - 1; i < insnSz; i++) {
    869                     Insn insn = insns.get(i);
    870                     if (insn.canThrow()) {
    871                         insn = insn.withAddedCatch(Type.OBJECT);
    872                         insns.set(i, insn);
    873                     }
    874                 }
    875             }
    876 
    877             if (primarySucc >= 0) {
    878                 newSucc.add(primarySucc);
    879             }
    880 
    881             newSucc.setImmutable();
    882             successors = newSucc;
    883         }
    884 
    885         // Construct the final resulting block(s), and store it (them).
    886 
    887         int primarySuccListIndex = successors.indexOf(primarySucc);
    888 
    889         /*
    890          * If there are any extra blocks, work backwards through the
    891          * list of instructions, adding single-instruction blocks, and
    892          * resetting the successors variables as appropriate.
    893          */
    894         for (/*extraBlockCount*/; extraBlockCount > 0; extraBlockCount--) {
    895             /*
    896              * Some of the blocks that the RopperMachine wants added
    897              * are for move-result insns, and these need goto insns as well.
    898              */
    899             Insn extraInsn = insns.get(--insnSz);
    900             boolean needsGoto
    901                     = extraInsn.getOpcode().getBranchingness()
    902                         == Rop.BRANCH_NONE;
    903             InsnList il = new InsnList(needsGoto ? 2 : 1);
    904             IntList extraBlockSuccessors = successors;
    905 
    906             il.set(0, extraInsn);
    907 
    908             if (needsGoto) {
    909                 il.set(1, new PlainInsn(Rops.GOTO,
    910                         extraInsn.getPosition(), null,
    911                         RegisterSpecList.EMPTY));
    912                 /*
    913                  * Obviously, this block won't be throwing an exception
    914                  * so it should only have one successor.
    915                  */
    916                 extraBlockSuccessors = IntList.makeImmutable(primarySucc);
    917             }
    918             il.setImmutable();
    919 
    920             int label = getAvailableLabel();
    921             BasicBlock bb = new BasicBlock(label, il, extraBlockSuccessors,
    922                     primarySucc);
    923             // All of these extra blocks will be in the same subroutine
    924             addBlock(bb, frame.getSubroutines());
    925 
    926             successors = successors.mutableCopy();
    927             successors.set(primarySuccListIndex, label);
    928             successors.setImmutable();
    929             primarySucc = label;
    930         }
    931 
    932         Insn lastInsn = (insnSz == 0) ? null : insns.get(insnSz - 1);
    933 
    934         /*
    935          * Add a goto to the end of the block if it doesn't already
    936          * end with a branch, to maintain the invariant that all
    937          * blocks end with a branch of some sort or other. Note that
    938          * it is possible for there to be blocks for which no
    939          * instructions were ever output (e.g., only consist of pop*
    940          * in the original Java bytecode).
    941          */
    942         if ((lastInsn == null) ||
    943             (lastInsn.getOpcode().getBranchingness() == Rop.BRANCH_NONE)) {
    944             SourcePosition pos = (lastInsn == null) ? SourcePosition.NO_INFO :
    945                 lastInsn.getPosition();
    946             insns.add(new PlainInsn(Rops.GOTO, pos, null,
    947                                     RegisterSpecList.EMPTY));
    948             insnSz++;
    949         }
    950 
    951         /*
    952          * Construct a block for the remaining instructions (which in
    953          * the usual case is all of them).
    954          */
    955 
    956         InsnList il = new InsnList(insnSz);
    957         for (int i = 0; i < insnSz; i++) {
    958             il.set(i, insns.get(i));
    959         }
    960         il.setImmutable();
    961 
    962         BasicBlock bb =
    963             new BasicBlock(block.getLabel(), il, successors, primarySucc);
    964         addOrReplaceBlock(bb, frame.getSubroutines());
    965     }
    966 
    967     /**
    968      * Helper for {@link #processBlock}, which merges frames and
    969      * adds to the work set, as necessary.
    970      *
    971      * @param label {@code >= 0;} label to work on
    972      * @param pred  predecessor label; must be {@code >= 0} when
    973      * {@code label} is a subroutine start block and calledSubroutine
    974      * is non-null. Otherwise, may be -1.
    975      * @param calledSubroutine {@code null-ok;} a Subroutine instance if
    976      * {@code label} is the first block in a subroutine.
    977      * @param frame {@code non-null;} new frame for the labelled block
    978      * @param workSet {@code non-null;} bits representing work to do,
    979      * which this method may add to
    980      */
    981     private void mergeAndWorkAsNecessary(int label, int pred,
    982             Subroutine calledSubroutine, Frame frame, int[] workSet) {
    983         Frame existing = startFrames[label];
    984         Frame merged;
    985 
    986         if (existing != null) {
    987             /*
    988              * Some other block also continues at this label. Merge
    989              * the frames, and re-set the bit in the work set if there
    990              * was a change.
    991              */
    992             if (calledSubroutine != null) {
    993                 merged = existing.mergeWithSubroutineCaller(frame,
    994                         calledSubroutine.getStartBlock(), pred);
    995             } else {
    996                 merged = existing.mergeWith(frame);
    997             }
    998             if (merged != existing) {
    999                 startFrames[label] = merged;
   1000                 Bits.set(workSet, label);
   1001             }
   1002         } else {
   1003             // This is the first time this label has been encountered.
   1004             if (calledSubroutine != null) {
   1005                 startFrames[label]
   1006                         = frame.makeNewSubroutineStartFrame(label, pred);
   1007             } else {
   1008                 startFrames[label] = frame;
   1009             }
   1010             Bits.set(workSet, label);
   1011         }
   1012     }
   1013 
   1014     /**
   1015      * Constructs and adds the blocks that perform setup for the rest of
   1016      * the method. This includes a first block which merely contains
   1017      * assignments from parameters to the same-numbered registers and
   1018      * a possible second block which deals with synchronization.
   1019      */
   1020     private void addSetupBlocks() {
   1021         LocalVariableList localVariables = method.getLocalVariables();
   1022         SourcePosition pos = method.makeSourcePosistion(0);
   1023         Prototype desc = method.getEffectiveDescriptor();
   1024         StdTypeList params = desc.getParameterTypes();
   1025         int sz = params.size();
   1026         InsnList insns = new InsnList(sz + 1);
   1027         int at = 0;
   1028 
   1029         for (int i = 0; i < sz; i++) {
   1030             Type one = params.get(i);
   1031             LocalVariableList.Item local =
   1032                 localVariables.pcAndIndexToLocal(0, at);
   1033             RegisterSpec result = (local == null) ?
   1034                 RegisterSpec.make(at, one) :
   1035                 RegisterSpec.makeLocalOptional(at, one, local.getLocalItem());
   1036 
   1037             Insn insn = new PlainCstInsn(Rops.opMoveParam(one), pos, result,
   1038                                          RegisterSpecList.EMPTY,
   1039                                          CstInteger.make(at));
   1040             insns.set(i, insn);
   1041             at += one.getCategory();
   1042         }
   1043 
   1044         insns.set(sz, new PlainInsn(Rops.GOTO, pos, null,
   1045                                     RegisterSpecList.EMPTY));
   1046         insns.setImmutable();
   1047 
   1048         boolean synch = isSynchronized();
   1049         int label = synch ? getSpecialLabel(SYNCH_SETUP_1) : 0;
   1050         BasicBlock bb =
   1051             new BasicBlock(getSpecialLabel(PARAM_ASSIGNMENT), insns,
   1052                            IntList.makeImmutable(label), label);
   1053         addBlock(bb, IntList.EMPTY);
   1054 
   1055         if (synch) {
   1056             RegisterSpec synchReg = getSynchReg();
   1057             Insn insn;
   1058             if (isStatic()) {
   1059                 insn = new ThrowingCstInsn(Rops.CONST_OBJECT, pos,
   1060                                            RegisterSpecList.EMPTY,
   1061                                            StdTypeList.EMPTY,
   1062                                            method.getDefiningClass());
   1063                 insns = new InsnList(1);
   1064                 insns.set(0, insn);
   1065             } else {
   1066                 insns = new InsnList(2);
   1067                 insn = new PlainCstInsn(Rops.MOVE_PARAM_OBJECT, pos,
   1068                                         synchReg, RegisterSpecList.EMPTY,
   1069                                         CstInteger.VALUE_0);
   1070                 insns.set(0, insn);
   1071                 insns.set(1, new PlainInsn(Rops.GOTO, pos, null,
   1072                                            RegisterSpecList.EMPTY));
   1073             }
   1074 
   1075             int label2 = getSpecialLabel(SYNCH_SETUP_2);
   1076             insns.setImmutable();
   1077             bb = new BasicBlock(label, insns,
   1078                                 IntList.makeImmutable(label2), label2);
   1079             addBlock(bb, IntList.EMPTY);
   1080 
   1081             insns = new InsnList(isStatic() ? 2 : 1);
   1082 
   1083             if (isStatic()) {
   1084                 insns.set(0, new PlainInsn(Rops.opMoveResultPseudo(synchReg),
   1085                         pos, synchReg, RegisterSpecList.EMPTY));
   1086             }
   1087 
   1088             insn = new ThrowingInsn(Rops.MONITOR_ENTER, pos,
   1089                                     RegisterSpecList.make(synchReg),
   1090                                     StdTypeList.EMPTY);
   1091             insns.set(isStatic() ? 1 :0, insn);
   1092             insns.setImmutable();
   1093             bb = new BasicBlock(label2, insns, IntList.makeImmutable(0), 0);
   1094             addBlock(bb, IntList.EMPTY);
   1095         }
   1096     }
   1097 
   1098     /**
   1099      * Constructs and adds the return block, if necessary. The return
   1100      * block merely contains an appropriate {@code return}
   1101      * instruction.
   1102      */
   1103     private void addReturnBlock() {
   1104         Rop returnOp = machine.getReturnOp();
   1105 
   1106         if (returnOp == null) {
   1107             /*
   1108              * The method being converted never returns normally, so there's
   1109              * no need for a return block.
   1110              */
   1111             return;
   1112         }
   1113 
   1114         SourcePosition returnPos = machine.getReturnPosition();
   1115         int label = getSpecialLabel(RETURN);
   1116 
   1117         if (isSynchronized()) {
   1118             InsnList insns = new InsnList(1);
   1119             Insn insn = new ThrowingInsn(Rops.MONITOR_EXIT, returnPos,
   1120                                          RegisterSpecList.make(getSynchReg()),
   1121                                          StdTypeList.EMPTY);
   1122             insns.set(0, insn);
   1123             insns.setImmutable();
   1124 
   1125             int nextLabel = getSpecialLabel(SYNCH_RETURN);
   1126             BasicBlock bb =
   1127                 new BasicBlock(label, insns,
   1128                                IntList.makeImmutable(nextLabel), nextLabel);
   1129             addBlock(bb, IntList.EMPTY);
   1130 
   1131             label = nextLabel;
   1132         }
   1133 
   1134         InsnList insns = new InsnList(1);
   1135         TypeList sourceTypes = returnOp.getSources();
   1136         RegisterSpecList sources;
   1137 
   1138         if (sourceTypes.size() == 0) {
   1139             sources = RegisterSpecList.EMPTY;
   1140         } else {
   1141             RegisterSpec source = RegisterSpec.make(0, sourceTypes.getType(0));
   1142             sources = RegisterSpecList.make(source);
   1143         }
   1144 
   1145         Insn insn = new PlainInsn(returnOp, returnPos, null, sources);
   1146         insns.set(0, insn);
   1147         insns.setImmutable();
   1148 
   1149         BasicBlock bb = new BasicBlock(label, insns, IntList.EMPTY, -1);
   1150         addBlock(bb, IntList.EMPTY);
   1151     }
   1152 
   1153     /**
   1154      * Constructs and adds, if necessary, the catch-all exception handler
   1155      * block to deal with unwinding the lock taken on entry to a synchronized
   1156      * method.
   1157      */
   1158     private void addSynchExceptionHandlerBlock() {
   1159         if (!synchNeedsExceptionHandler) {
   1160             /*
   1161              * The method being converted either isn't synchronized or
   1162              * can't possibly throw exceptions in its main body, so
   1163              * there's no need for a synchronized method exception
   1164              * handler.
   1165              */
   1166             return;
   1167         }
   1168 
   1169         SourcePosition pos = method.makeSourcePosistion(0);
   1170         RegisterSpec exReg = RegisterSpec.make(0, Type.THROWABLE);
   1171         BasicBlock bb;
   1172         Insn insn;
   1173 
   1174         InsnList insns = new InsnList(2);
   1175         insn = new PlainInsn(Rops.opMoveException(Type.THROWABLE), pos,
   1176                              exReg, RegisterSpecList.EMPTY);
   1177         insns.set(0, insn);
   1178         insn = new ThrowingInsn(Rops.MONITOR_EXIT, pos,
   1179                                 RegisterSpecList.make(getSynchReg()),
   1180                                 StdTypeList.EMPTY);
   1181         insns.set(1, insn);
   1182         insns.setImmutable();
   1183 
   1184         int label2 = getSpecialLabel(SYNCH_CATCH_2);
   1185         bb = new BasicBlock(getSpecialLabel(SYNCH_CATCH_1), insns,
   1186                             IntList.makeImmutable(label2), label2);
   1187         addBlock(bb, IntList.EMPTY);
   1188 
   1189         insns = new InsnList(1);
   1190         insn = new ThrowingInsn(Rops.THROW, pos,
   1191                                 RegisterSpecList.make(exReg),
   1192                                 StdTypeList.EMPTY);
   1193         insns.set(0, insn);
   1194         insns.setImmutable();
   1195 
   1196         bb = new BasicBlock(label2, insns, IntList.EMPTY, -1);
   1197         addBlock(bb, IntList.EMPTY);
   1198     }
   1199 
   1200     /**
   1201      * Creates the exception handler setup blocks. "maxLocals"
   1202      * below is because that's the register number corresponding
   1203      * to the sole element on a one-deep stack (which is the
   1204      * situation at the start of an exception handler block).
   1205      */
   1206     private void addExceptionSetupBlocks() {
   1207 
   1208         int len = catchTypes.length;
   1209         for (int i = 0; i < len; i++) {
   1210             Type one = catchTypes[i];
   1211             if (one != null) {
   1212                 Insn proto = labelToBlock(i).getFirstInsn();
   1213                 SourcePosition pos = proto.getPosition();
   1214                 InsnList il = new InsnList(2);
   1215 
   1216                 Insn insn = new PlainInsn(Rops.opMoveException(one),
   1217                                           pos,
   1218                                           RegisterSpec.make(maxLocals, one),
   1219                                           RegisterSpecList.EMPTY);
   1220                 il.set(0, insn);
   1221 
   1222                 insn = new PlainInsn(Rops.GOTO, pos, null,
   1223                                      RegisterSpecList.EMPTY);
   1224                 il.set(1, insn);
   1225                 il.setImmutable();
   1226 
   1227                 BasicBlock bb = new BasicBlock(getExceptionSetupLabel(i),
   1228                                                il,
   1229                                                IntList.makeImmutable(i),
   1230                                                i);
   1231                 addBlock(bb, startFrames[i].getSubroutines());
   1232             }
   1233         }
   1234     }
   1235 
   1236     /**
   1237      * Checks to see if the basic block is a subroutine caller block.
   1238      *
   1239      * @param bb {@code non-null;} the basic block in question
   1240      * @return true if this block calls a subroutine
   1241      */
   1242     private boolean isSubroutineCaller(BasicBlock bb) {
   1243         IntList successors = bb.getSuccessors();
   1244         if (successors.size() < 2) return false;
   1245 
   1246         int subLabel = successors.get(1);
   1247 
   1248         return (subLabel < subroutines.length)
   1249                 && (subroutines[subLabel] != null);
   1250     }
   1251 
   1252     /**
   1253      * Inlines any subroutine calls.
   1254      */
   1255     private void inlineSubroutines() {
   1256         final IntList reachableSubroutineCallerLabels = new IntList(4);
   1257 
   1258         /*
   1259          * Compile a list of all subroutine calls reachable
   1260          * through the normal (non-subroutine) flow.  We do this first, since
   1261          * we'll be affecting the call flow as we go.
   1262          *
   1263          * Start at label 0 --  the param assignment block has nothing for us
   1264          */
   1265         forEachNonSubBlockDepthFirst(0, new BasicBlock.Visitor() {
   1266             public void visitBlock(BasicBlock b) {
   1267                 if (isSubroutineCaller(b)) {
   1268                     reachableSubroutineCallerLabels.add(b.getLabel());
   1269                 }
   1270             }
   1271         });
   1272 
   1273         /*
   1274          * Convert the resultSubroutines list, indexed by block index,
   1275          * to a label-to-subroutines mapping used by the inliner.
   1276          */
   1277         int largestAllocedLabel = getAvailableLabel();
   1278         ArrayList<IntList> labelToSubroutines
   1279                 = new ArrayList<IntList>(largestAllocedLabel);
   1280         for (int i = 0; i < largestAllocedLabel; i++) {
   1281             labelToSubroutines.add(null);
   1282         }
   1283 
   1284         for (int i = 0; i < result.size(); i++) {
   1285             BasicBlock b = result.get(i);
   1286             if (b == null) {
   1287                 continue;
   1288             }
   1289             IntList subroutineList = resultSubroutines.get(i);
   1290             labelToSubroutines.set(b.getLabel(), subroutineList);
   1291         }
   1292 
   1293         /*
   1294          * Inline all reachable subroutines.
   1295          * Inner subroutines will be inlined as they are encountered.
   1296          */
   1297         int sz = reachableSubroutineCallerLabels.size();
   1298         for (int i = 0 ; i < sz ; i++) {
   1299             int label = reachableSubroutineCallerLabels.get(i);
   1300             new SubroutineInliner(
   1301                     new LabelAllocator(getAvailableLabel()),
   1302                     labelToSubroutines)
   1303                     .inlineSubroutineCalledFrom(labelToBlock(label));
   1304         }
   1305 
   1306         // Now find the blocks that aren't reachable and remove them
   1307         deleteUnreachableBlocks();
   1308     }
   1309 
   1310     /**
   1311      * Deletes all blocks that cannot be reached. This is run to delete
   1312      * original subroutine blocks after subroutine inlining.
   1313      */
   1314     private void deleteUnreachableBlocks() {
   1315         final IntList reachableLabels = new IntList(result.size());
   1316 
   1317         // subroutine inlining is done now and we won't update this list here
   1318         resultSubroutines.clear();
   1319 
   1320         forEachNonSubBlockDepthFirst(getSpecialLabel(PARAM_ASSIGNMENT),
   1321                 new BasicBlock.Visitor() {
   1322 
   1323             public void visitBlock(BasicBlock b) {
   1324                 reachableLabels.add(b.getLabel());
   1325             }
   1326         });
   1327 
   1328         reachableLabels.sort();
   1329 
   1330         for (int i = result.size() - 1 ; i >= 0 ; i--) {
   1331             if (reachableLabels.indexOf(result.get(i).getLabel()) < 0) {
   1332                 result.remove(i);
   1333                 // unnecessary here really, since subroutine inlining is done
   1334                 //resultSubroutines.remove(i);
   1335             }
   1336         }
   1337     }
   1338 
   1339     /**
   1340      * Allocates labels, without requiring previously allocated labels
   1341      * to have been added to the blocks list.
   1342      */
   1343     private static class LabelAllocator {
   1344         int nextAvailableLabel;
   1345 
   1346         /**
   1347          * @param startLabel available label to start allocating from
   1348          */
   1349         LabelAllocator(int startLabel) {
   1350             nextAvailableLabel = startLabel;
   1351         }
   1352 
   1353         /**
   1354          * @return next available label
   1355          */
   1356         int getNextLabel() {
   1357             return nextAvailableLabel++;
   1358         }
   1359     }
   1360 
   1361     /**
   1362      * Inlines a subroutine. Start by calling
   1363      * {@link #inlineSubroutineCalledFrom}.
   1364      */
   1365     private class SubroutineInliner {
   1366         /**
   1367          * maps original label to the label that will be used by the
   1368          * inlined version
   1369          */
   1370         private final HashMap<Integer, Integer> origLabelToCopiedLabel;
   1371 
   1372         /** set of original labels that need to be copied */
   1373         private final BitSet workList;
   1374 
   1375         /** the label of the original start block for this subroutine */
   1376         private int subroutineStart;
   1377 
   1378         /** the label of the ultimate return block */
   1379         private int subroutineSuccessor;
   1380 
   1381         /** used for generating new labels for copied blocks */
   1382         private final LabelAllocator labelAllocator;
   1383 
   1384         /**
   1385          * A mapping, indexed by label, to subroutine nesting list.
   1386          * The subroutine nest list is as returned by
   1387          * {@link Frame#getSubroutines}.
   1388          */
   1389         private final ArrayList<IntList> labelToSubroutines;
   1390 
   1391         SubroutineInliner(final LabelAllocator labelAllocator,
   1392                 ArrayList<IntList> labelToSubroutines) {
   1393             origLabelToCopiedLabel = new HashMap<Integer, Integer>();
   1394 
   1395             workList = new BitSet(maxLabel);
   1396 
   1397             this.labelAllocator = labelAllocator;
   1398             this.labelToSubroutines = labelToSubroutines;
   1399         }
   1400 
   1401         /**
   1402          * Inlines a subroutine.
   1403          *
   1404          * @param b block where {@code jsr} occurred in the original bytecode
   1405          */
   1406         void inlineSubroutineCalledFrom(final BasicBlock b) {
   1407             /*
   1408              * The 0th successor of a subroutine caller block is where
   1409              * the subroutine should return to. The 1st successor is
   1410              * the start block of the subroutine.
   1411              */
   1412             subroutineSuccessor = b.getSuccessors().get(0);
   1413             subroutineStart = b.getSuccessors().get(1);
   1414 
   1415             /*
   1416              * This allocates an initial label and adds the first
   1417              * block to the worklist.
   1418              */
   1419             int newSubStartLabel = mapOrAllocateLabel(subroutineStart);
   1420 
   1421             for (int label = workList.nextSetBit(0); label >= 0;
   1422                  label = workList.nextSetBit(0)) {
   1423                 workList.clear(label);
   1424                 int newLabel = origLabelToCopiedLabel.get(label);
   1425 
   1426                 copyBlock(label, newLabel);
   1427 
   1428                 if (isSubroutineCaller(labelToBlock(label))) {
   1429                     new SubroutineInliner(labelAllocator, labelToSubroutines)
   1430                         .inlineSubroutineCalledFrom(labelToBlock(newLabel));
   1431                 }
   1432             }
   1433 
   1434             /*
   1435              * Replace the original caller block, since we now have a
   1436              * new successor
   1437              */
   1438 
   1439             addOrReplaceBlockNoDelete(
   1440                 new BasicBlock(b.getLabel(), b.getInsns(),
   1441                     IntList.makeImmutable (newSubStartLabel),
   1442                             newSubStartLabel),
   1443                 labelToSubroutines.get(b.getLabel()));
   1444         }
   1445 
   1446         /**
   1447          * Copies a basic block, mapping its successors along the way.
   1448          *
   1449          * @param origLabel original block label
   1450          * @param newLabel label that the new block should have
   1451          */
   1452         private void copyBlock(int origLabel, int newLabel) {
   1453 
   1454             BasicBlock origBlock = labelToBlock(origLabel);
   1455 
   1456             final IntList origSuccessors = origBlock.getSuccessors();
   1457             IntList successors;
   1458             int primarySuccessor = -1;
   1459             Subroutine subroutine;
   1460 
   1461             if (isSubroutineCaller(origBlock)) {
   1462                 /*
   1463                  * A subroutine call inside a subroutine call.
   1464                  * Set up so we can recurse. The caller block should have
   1465                  * it's first successor be a copied block that will be
   1466                  * the subroutine's return point. It's second successor will
   1467                  * be copied when we recurse, and remains as the original
   1468                  * label of the start of the inner subroutine.
   1469                  */
   1470 
   1471                 successors = IntList.makeImmutable(
   1472                         mapOrAllocateLabel(origSuccessors.get(0)),
   1473                         origSuccessors.get(1));
   1474                 // primary successor will be set when this block is replaced
   1475             } else if (null
   1476                     != (subroutine = subroutineFromRetBlock(origLabel))) {
   1477                 /*
   1478                  * this is a ret block -- its successor
   1479                  * should be subroutineSuccessor
   1480                  */
   1481 
   1482                 // Sanity check
   1483                 if (subroutine.startBlock != subroutineStart) {
   1484                     throw new RuntimeException (
   1485                             "ret instruction returns to label "
   1486                             + Hex.u2 (subroutine.startBlock)
   1487                             + " expected: " + Hex.u2(subroutineStart));
   1488                 }
   1489 
   1490                 successors = IntList.makeImmutable(subroutineSuccessor);
   1491                 primarySuccessor = subroutineSuccessor;
   1492             } else {
   1493                 // Map all the successor labels
   1494 
   1495                 int origPrimary = origBlock.getPrimarySuccessor();
   1496                 int sz = origSuccessors.size();
   1497 
   1498                 successors = new IntList(sz);
   1499 
   1500                 for (int i = 0 ; i < sz ; i++) {
   1501                     int origSuccLabel = origSuccessors.get(i);
   1502                     int newSuccLabel =  mapOrAllocateLabel(origSuccLabel);
   1503 
   1504                     successors.add(newSuccLabel);
   1505 
   1506                     if (origPrimary == origSuccLabel) {
   1507                         primarySuccessor = newSuccLabel;
   1508                     }
   1509                 }
   1510 
   1511                 successors.setImmutable();
   1512             }
   1513 
   1514             addBlock (
   1515                 new BasicBlock(newLabel,
   1516                     filterMoveReturnAddressInsns(origBlock.getInsns()),
   1517                     successors, primarySuccessor),
   1518                     labelToSubroutines.get(newLabel));
   1519         }
   1520 
   1521         /**
   1522          * Checks to see if a specified label is involved in a specified
   1523          * subroutine.
   1524          *
   1525          * @param label {@code >= 0;} a basic block label
   1526          * @param subroutineStart {@code >= 0;} a subroutine as identified
   1527          * by the label of its start block
   1528          * @return true if the block is dominated by the subroutine call
   1529          */
   1530         private boolean involvedInSubroutine(int label, int subroutineStart) {
   1531             IntList subroutinesList = labelToSubroutines.get(label);
   1532             return (subroutinesList != null && subroutinesList.size() > 0
   1533                     && subroutinesList.top() == subroutineStart);
   1534         }
   1535 
   1536         /**
   1537          * Maps the label of a pre-copied block to the label of the inlined
   1538          * block, allocating a new label and adding it to the worklist
   1539          * if necessary.  If the origLabel is a "special" label, it
   1540          * is returned exactly and not scheduled for duplication: copying
   1541          * never proceeds past a special label, which likely is the function
   1542          * return block or an immediate predecessor.
   1543          *
   1544          * @param origLabel label of original, pre-copied block
   1545          * @return label for new, inlined block
   1546          */
   1547         private int mapOrAllocateLabel(int origLabel) {
   1548             int resultLabel;
   1549             Integer mappedLabel = origLabelToCopiedLabel.get(origLabel);
   1550 
   1551             if (mappedLabel != null) {
   1552                 resultLabel = mappedLabel;
   1553             } else if (!involvedInSubroutine(origLabel,subroutineStart)) {
   1554                 /*
   1555                  * A subroutine has ended by some means other than a "ret"
   1556                  * (which really means a throw caught later).
   1557                  */
   1558                 resultLabel = origLabel;
   1559             } else {
   1560                 resultLabel = labelAllocator.getNextLabel();
   1561                 workList.set(origLabel);
   1562                 origLabelToCopiedLabel.put(origLabel, resultLabel);
   1563 
   1564                 // The new label has the same frame as the original label
   1565                 while (labelToSubroutines.size() <= resultLabel) {
   1566                     labelToSubroutines.add(null);
   1567                 }
   1568                 labelToSubroutines.set(resultLabel,
   1569                         labelToSubroutines.get(origLabel));
   1570             }
   1571 
   1572             return resultLabel;
   1573         }
   1574     }
   1575 
   1576     /**
   1577      * Finds a {@code Subroutine} that is returned from by a {@code ret} in
   1578      * a given block.
   1579      *
   1580      * @param label A block that originally contained a {@code ret} instruction
   1581      * @return {@code null-ok;} found subroutine or {@code null} if none
   1582      * was found
   1583      */
   1584     private Subroutine subroutineFromRetBlock(int label) {
   1585         for (int i = subroutines.length - 1 ; i >= 0 ; i--) {
   1586             if (subroutines[i] != null) {
   1587                 Subroutine subroutine = subroutines[i];
   1588 
   1589                 if (subroutine.retBlocks.get(label)) {
   1590                     return subroutine;
   1591                 }
   1592             }
   1593         }
   1594 
   1595         return null;
   1596     }
   1597 
   1598 
   1599     /**
   1600      * Removes all {@code move-return-address} instructions, returning a new
   1601      * {@code InsnList} if necessary. The {@code move-return-address}
   1602      * insns are dead code after subroutines have been inlined.
   1603      *
   1604      * @param insns {@code InsnList} that may contain
   1605      * {@code move-return-address} insns
   1606      * @return {@code InsnList} with {@code move-return-address} removed
   1607      */
   1608     private InsnList filterMoveReturnAddressInsns(InsnList insns) {
   1609         int sz;
   1610         int newSz = 0;
   1611 
   1612         // First see if we need to filter, and if so what the new size will be
   1613         sz = insns.size();
   1614         for (int i = 0; i < sz; i++) {
   1615             if (insns.get(i).getOpcode() != Rops.MOVE_RETURN_ADDRESS) {
   1616                 newSz++;
   1617             }
   1618         }
   1619 
   1620         if (newSz == sz) {
   1621             return insns;
   1622         }
   1623 
   1624         // Make a new list without the MOVE_RETURN_ADDRESS insns
   1625         InsnList newInsns = new InsnList(newSz);
   1626 
   1627         int newIndex = 0;
   1628         for (int i = 0; i < sz; i++) {
   1629             Insn insn = insns.get(i);
   1630             if (insn.getOpcode() != Rops.MOVE_RETURN_ADDRESS) {
   1631                 newInsns.set(newIndex++, insn);
   1632             }
   1633         }
   1634 
   1635         newInsns.setImmutable();
   1636         return newInsns;
   1637     }
   1638 
   1639     /**
   1640      * Visits each non-subroutine block once in depth-first successor order.
   1641      *
   1642      * @param firstLabel label of start block
   1643      * @param v callback interface
   1644      */
   1645     private void forEachNonSubBlockDepthFirst(int firstLabel,
   1646             BasicBlock.Visitor v) {
   1647         forEachNonSubBlockDepthFirst0(labelToBlock(firstLabel),
   1648                 v, new BitSet(maxLabel));
   1649     }
   1650 
   1651     /**
   1652      * Visits each block once in depth-first successor order, ignoring
   1653      * {@code jsr} targets. Worker for {@link #forEachNonSubBlockDepthFirst}.
   1654      *
   1655      * @param next next block to visit
   1656      * @param v callback interface
   1657      * @param visited set of blocks already visited
   1658      */
   1659     private void forEachNonSubBlockDepthFirst0(
   1660             BasicBlock next, BasicBlock.Visitor v, BitSet visited) {
   1661         v.visitBlock(next);
   1662         visited.set(next.getLabel());
   1663 
   1664         IntList successors = next.getSuccessors();
   1665         int sz = successors.size();
   1666 
   1667         for (int i = 0; i < sz; i++) {
   1668             int succ = successors.get(i);
   1669 
   1670             if (visited.get(succ)) {
   1671                 continue;
   1672             }
   1673 
   1674             if (isSubroutineCaller(next) && i > 0) {
   1675                 // ignore jsr targets
   1676                 continue;
   1677             }
   1678 
   1679             /*
   1680              * Ignore missing labels: they're successors of
   1681              * subroutines that never invoke a ret.
   1682              */
   1683             int idx = labelToResultIndex(succ);
   1684             if (idx >= 0) {
   1685                 forEachNonSubBlockDepthFirst0(result.get(idx), v, visited);
   1686             }
   1687         }
   1688     }
   1689 }
   1690