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.rop.code;
     18 
     19 import com.android.dx.rop.type.StdTypeList;
     20 import com.android.dx.rop.type.TypeList;
     21 import com.android.dx.util.Hex;
     22 import com.android.dx.util.IntList;
     23 import com.android.dx.util.LabeledList;
     24 
     25 /**
     26  * List of {@link BasicBlock} instances.
     27  */
     28 public final class BasicBlockList extends LabeledList {
     29     /**
     30      * {@code >= -1;} the count of registers required by this method or
     31      * {@code -1} if not yet calculated
     32      */
     33     private int regCount;
     34 
     35     /**
     36      * Constructs an instance. All indices initially contain {@code null},
     37      * and the first-block label is initially {@code -1}.
     38      *
     39      * @param size the size of the list
     40      */
     41     public BasicBlockList(int size) {
     42         super(size);
     43 
     44         regCount = -1;
     45     }
     46 
     47     /**
     48      * Constructs a mutable copy for {@code getMutableCopy()}.
     49      *
     50      * @param old block to copy
     51      */
     52     private BasicBlockList(BasicBlockList old) {
     53         super(old);
     54         regCount = old.regCount;
     55     }
     56 
     57 
     58     /**
     59      * Gets the element at the given index. It is an error to call
     60      * this with the index for an element which was never set; if you
     61      * do that, this will throw {@code NullPointerException}.
     62      *
     63      * @param n {@code >= 0, < size();} which index
     64      * @return {@code non-null;} element at that index
     65      */
     66     public BasicBlock get(int n) {
     67         return (BasicBlock) get0(n);
     68     }
     69 
     70     /**
     71      * Sets the basic block at the given index.
     72      *
     73      * @param n {@code >= 0, < size();} which index
     74      * @param bb {@code null-ok;} the element to set at {@code n}
     75      */
     76     public void set(int n, BasicBlock bb) {
     77         super.set(n, bb);
     78 
     79         // Reset regCount, since it will need to be recalculated.
     80         regCount = -1;
     81     }
     82 
     83     /**
     84      * Returns how many registers this method requires. This is simply
     85      * the maximum of register-number-plus-category referred to by this
     86      * instance's instructions (indirectly through {@link BasicBlock}
     87      * instances).
     88      *
     89      * @return {@code >= 0;} the register count
     90      */
     91     public int getRegCount() {
     92         if (regCount == -1) {
     93             RegCountVisitor visitor = new RegCountVisitor();
     94             forEachInsn(visitor);
     95             regCount = visitor.getRegCount();
     96         }
     97 
     98         return regCount;
     99     }
    100 
    101     /**
    102      * Gets the total instruction count for this instance. This is the
    103      * sum of the instruction counts of each block.
    104      *
    105      * @return {@code >= 0;} the total instruction count
    106      */
    107     public int getInstructionCount() {
    108         int sz = size();
    109         int result = 0;
    110 
    111         for (int i = 0; i < sz; i++) {
    112             BasicBlock one = (BasicBlock) getOrNull0(i);
    113             if (one != null) {
    114                 result += one.getInsns().size();
    115             }
    116         }
    117 
    118         return result;
    119     }
    120 
    121     /**
    122      * Gets the total instruction count for this instance, ignoring
    123      * mark-local instructions which are not actually emitted.
    124      *
    125      * @return {@code >= 0;} the total instruction count
    126      */
    127     public int getEffectiveInstructionCount() {
    128         int sz = size();
    129         int result = 0;
    130 
    131         for (int i = 0; i < sz; i++) {
    132             BasicBlock one = (BasicBlock) getOrNull0(i);
    133             if (one != null) {
    134                 InsnList insns = one.getInsns();
    135                 int insnsSz = insns.size();
    136 
    137                 for (int j = 0; j < insnsSz; j++) {
    138                     Insn insn = insns.get(j);
    139 
    140                     if (insn.getOpcode().getOpcode() != RegOps.MARK_LOCAL) {
    141                         result++;
    142                     }
    143                 }
    144             }
    145         }
    146 
    147         return result;
    148     }
    149 
    150     /**
    151      * Gets the first block in the list with the given label, if any.
    152      *
    153      * @param label {@code >= 0;} the label to look for
    154      * @return {@code non-null;} the so-labelled block
    155      * @throws IllegalArgumentException thrown if the label isn't found
    156      */
    157     public BasicBlock labelToBlock(int label) {
    158         int idx = indexOfLabel(label);
    159 
    160         if (idx < 0) {
    161             throw new IllegalArgumentException("no such label: "
    162                     + Hex.u2(label));
    163         }
    164 
    165         return get(idx);
    166     }
    167 
    168     /**
    169      * Visits each instruction of each block in the list, in order.
    170      *
    171      * @param visitor {@code non-null;} visitor to use
    172      */
    173     public void forEachInsn(Insn.Visitor visitor) {
    174         int sz = size();
    175 
    176         for (int i = 0; i < sz; i++) {
    177             BasicBlock one = get(i);
    178             InsnList insns = one.getInsns();
    179             insns.forEach(visitor);
    180         }
    181     }
    182 
    183     /**
    184      * Returns an instance that is identical to this one, except that
    185      * the registers in each instruction are offset by the given
    186      * amount. Mutability of the result is inherited from the
    187      * original.
    188      *
    189      * @param delta the amount to offset register numbers by
    190      * @return {@code non-null;} an appropriately-constructed instance
    191      */
    192     public BasicBlockList withRegisterOffset(int delta) {
    193         int sz = size();
    194         BasicBlockList result = new BasicBlockList(sz);
    195 
    196         for (int i = 0; i < sz; i++) {
    197             BasicBlock one = (BasicBlock) get0(i);
    198             if (one != null) {
    199                 result.set(i, one.withRegisterOffset(delta));
    200             }
    201         }
    202 
    203         if (isImmutable()) {
    204             result.setImmutable();
    205         }
    206 
    207         return result;
    208     }
    209 
    210     /**
    211      * Returns a mutable copy of this list.
    212      *
    213      * @return {@code non-null;} an appropriately-constructed instance
    214      */
    215     public BasicBlockList getMutableCopy() {
    216         return new BasicBlockList(this);
    217     }
    218 
    219     /**
    220      * Gets the preferred successor for the given block. If the block
    221      * only has one successor, then that is the preferred successor.
    222      * Otherwise, if the block has a primay successor, then that is
    223      * the preferred successor. If the block has no successors, then
    224      * this returns {@code null}.
    225      *
    226      * @param block {@code non-null;} the block in question
    227      * @return {@code null-ok;} the preferred successor, if any
    228      */
    229     public BasicBlock preferredSuccessorOf(BasicBlock block) {
    230         int primarySuccessor = block.getPrimarySuccessor();
    231         IntList successors = block.getSuccessors();
    232         int succSize = successors.size();
    233 
    234         switch (succSize) {
    235             case 0: {
    236                 return null;
    237             }
    238             case 1: {
    239                 return labelToBlock(successors.get(0));
    240             }
    241         }
    242 
    243         if (primarySuccessor != -1) {
    244             return labelToBlock(primarySuccessor);
    245         } else {
    246             return labelToBlock(successors.get(0));
    247         }
    248     }
    249 
    250     /**
    251      * Compares the catches of two blocks for equality. This includes
    252      * both the catch types and target labels.
    253      *
    254      * @param block1 {@code non-null;} one block to compare
    255      * @param block2 {@code non-null;} the other block to compare
    256      * @return {@code true} if the two blocks' non-primary successors
    257      * are identical
    258      */
    259     public boolean catchesEqual(BasicBlock block1, BasicBlock block2) {
    260         TypeList catches1 = block1.getExceptionHandlerTypes();
    261         TypeList catches2 = block2.getExceptionHandlerTypes();
    262 
    263         if (!StdTypeList.equalContents(catches1, catches2)) {
    264             return false;
    265         }
    266 
    267         IntList succ1 = block1.getSuccessors();
    268         IntList succ2 = block2.getSuccessors();
    269         int size = succ1.size(); // Both are guaranteed to be the same size.
    270 
    271         int primary1 = block1.getPrimarySuccessor();
    272         int primary2 = block2.getPrimarySuccessor();
    273 
    274         if (((primary1 == -1) || (primary2 == -1))
    275                 && (primary1 != primary2)) {
    276             /*
    277              * For the current purpose, both blocks in question must
    278              * either both have a primary or both not have a primary to
    279              * be considered equal, and it turns out here that that's not
    280              * the case.
    281              */
    282             return false;
    283         }
    284 
    285         for (int i = 0; i < size; i++) {
    286             int label1 = succ1.get(i);
    287             int label2 = succ2.get(i);
    288 
    289             if (label1 == primary1) {
    290                 /*
    291                  * It should be the case that block2's primary is at the
    292                  * same index. If not, we consider the blocks unequal for
    293                  * the current purpose.
    294                  */
    295                 if (label2 != primary2) {
    296                     return false;
    297                 }
    298                 continue;
    299             }
    300 
    301             if (label1 != label2) {
    302                 return false;
    303             }
    304         }
    305 
    306         return true;
    307     }
    308 
    309     /**
    310      * Instruction visitor class for counting registers used.
    311      */
    312     private static class RegCountVisitor
    313             implements Insn.Visitor {
    314         /** {@code >= 0;} register count in-progress */
    315         private int regCount;
    316 
    317         /**
    318          * Constructs an instance.
    319          */
    320         public RegCountVisitor() {
    321             regCount = 0;
    322         }
    323 
    324         /**
    325          * Gets the register count.
    326          *
    327          * @return {@code >= 0;} the count
    328          */
    329         public int getRegCount() {
    330             return regCount;
    331         }
    332 
    333         /** {@inheritDoc} */
    334         public void visitPlainInsn(PlainInsn insn) {
    335             visit(insn);
    336         }
    337 
    338         /** {@inheritDoc} */
    339         public void visitPlainCstInsn(PlainCstInsn insn) {
    340             visit(insn);
    341         }
    342 
    343         /** {@inheritDoc} */
    344         public void visitSwitchInsn(SwitchInsn insn) {
    345             visit(insn);
    346         }
    347 
    348         /** {@inheritDoc} */
    349         public void visitThrowingCstInsn(ThrowingCstInsn insn) {
    350             visit(insn);
    351         }
    352 
    353         /** {@inheritDoc} */
    354         public void visitThrowingInsn(ThrowingInsn insn) {
    355             visit(insn);
    356         }
    357 
    358         /** {@inheritDoc} */
    359         public void visitFillArrayDataInsn(FillArrayDataInsn insn) {
    360             visit(insn);
    361         }
    362 
    363         /**
    364          * Helper for all the {@code visit*} methods.
    365          *
    366          * @param insn {@code non-null;} instruction being visited
    367          */
    368         private void visit(Insn insn) {
    369             RegisterSpec result = insn.getResult();
    370 
    371             if (result != null) {
    372                 processReg(result);
    373             }
    374 
    375             RegisterSpecList sources = insn.getSources();
    376             int sz = sources.size();
    377 
    378             for (int i = 0; i < sz; i++) {
    379                 processReg(sources.get(i));
    380             }
    381         }
    382 
    383         /**
    384          * Processes the given register spec.
    385          *
    386          * @param spec {@code non-null;} the register spec
    387          */
    388         private void processReg(RegisterSpec spec) {
    389             int reg = spec.getNextReg();
    390 
    391             if (reg > regCount) {
    392                 regCount = reg;
    393             }
    394         }
    395     }
    396 }
    397