Home | History | Annotate | Download | only in back 
      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.ssa.back;
     18 
     19 import com.android.dx.rop.code.BasicBlock;
     20 import com.android.dx.rop.code.BasicBlockList;
     21 import com.android.dx.rop.code.CstInsn;
     22 import com.android.dx.rop.code.Insn;
     23 import com.android.dx.rop.code.InsnList;
     24 import com.android.dx.rop.code.RegOps;
     25 import com.android.dx.rop.code.RopMethod;
     26 import com.android.dx.rop.code.SwitchInsn;
     27 import com.android.dx.util.IntList;
     28 
     29 import java.util.BitSet;
     30 
     31 /**
     32  * Searches for basic blocks that all have the same successor and insns
     33  * but different predecessors. These blocks are then combined into a single
     34  * block and the now-unused blocks are deleted. These identical blocks
     35  * frequently are created when catch blocks are edge-split.
     36  */
     37 public class IdenticalBlockCombiner {
     38     private final RopMethod ropMethod;
     39     private final BasicBlockList blocks;
     40     private final BasicBlockList newBlocks;
     41 
     42     /**
     43      * Constructs instance. Call {@code process()} to run.
     44      *
     45      * @param rm {@code non-null;} instance to process
     46      */
     47     public IdenticalBlockCombiner(RopMethod rm) {
     48         ropMethod = rm;
     49         blocks = ropMethod.getBlocks();
     50         newBlocks = blocks.getMutableCopy();
     51     }
     52 
     53     /**
     54      * Runs algorithm. TODO: This is n^2, and could be made linear-ish with
     55      * a hash. In particular, hash the contents of each block and only
     56      * compare blocks with the same hash.
     57      *
     58      * @return {@code non-null;} new method that has been processed
     59      */
     60     public RopMethod process() {
     61         int szBlocks = blocks.size();
     62         // indexed by label
     63         BitSet toDelete = new BitSet(blocks.getMaxLabel());
     64 
     65         // For each non-deleted block...
     66         for (int bindex = 0; bindex < szBlocks; bindex++) {
     67             BasicBlock b = blocks.get(bindex);
     68 
     69             if (toDelete.get(b.getLabel())) {
     70                 // doomed block
     71                 continue;
     72             }
     73 
     74             IntList preds = ropMethod.labelToPredecessors(b.getLabel());
     75 
     76             // ...look at all of it's predecessors that have only one succ...
     77             int szPreds = preds.size();
     78             for (int i = 0; i < szPreds; i++) {
     79                 int iLabel = preds.get(i);
     80 
     81                 BasicBlock iBlock = blocks.labelToBlock(iLabel);
     82 
     83                 if (toDelete.get(iLabel)
     84                         || iBlock.getSuccessors().size() > 1
     85                         || iBlock.getFirstInsn().getOpcode().getOpcode() ==
     86                             RegOps.MOVE_RESULT) {
     87                     continue;
     88                 }
     89 
     90                 IntList toCombine = new IntList();
     91 
     92                 // ...and see if they can be combined with any other preds...
     93                 for (int j = i + 1; j < szPreds; j++) {
     94                     int jLabel = preds.get(j);
     95                     BasicBlock jBlock = blocks.labelToBlock(jLabel);
     96 
     97                     if (jBlock.getSuccessors().size() == 1
     98                             && compareInsns(iBlock, jBlock)) {
     99 
    100                         toCombine.add(jLabel);
    101                         toDelete.set(jLabel);
    102                     }
    103                 }
    104 
    105                 combineBlocks(iLabel, toCombine);
    106             }
    107         }
    108 
    109         for (int i = szBlocks - 1; i >= 0; i--) {
    110             if (toDelete.get(newBlocks.get(i).getLabel())) {
    111                 newBlocks.set(i, null);
    112             }
    113         }
    114 
    115         newBlocks.shrinkToFit();
    116         newBlocks.setImmutable();
    117 
    118         return new RopMethod(newBlocks, ropMethod.getFirstLabel());
    119     }
    120 
    121     /**
    122      * Helper method to compare the contents of two blocks.
    123      *
    124      * @param a {@code non-null;} a block to compare
    125      * @param b {@code non-null;} another block to compare
    126      * @return {@code true} iff the two blocks' instructions are the same
    127      */
    128     private static boolean compareInsns(BasicBlock a, BasicBlock b) {
    129         return a.getInsns().contentEquals(b.getInsns());
    130     }
    131 
    132     /**
    133      * Combines blocks proven identical into one alpha block, re-writing
    134      * all of the successor links that point to the beta blocks to point
    135      * to the alpha block instead.
    136      *
    137      * @param alphaLabel block that will replace all the beta block
    138      * @param betaLabels label list of blocks to combine
    139      */
    140     private void combineBlocks(int alphaLabel, IntList betaLabels) {
    141         int szBetas = betaLabels.size();
    142 
    143         for (int i = 0; i < szBetas; i++) {
    144             int betaLabel = betaLabels.get(i);
    145             BasicBlock bb = blocks.labelToBlock(betaLabel);
    146             IntList preds = ropMethod.labelToPredecessors(bb.getLabel());
    147             int szPreds = preds.size();
    148 
    149             for (int j = 0; j < szPreds; j++) {
    150                 BasicBlock predBlock = newBlocks.labelToBlock(preds.get(j));
    151                 replaceSucc(predBlock, betaLabel, alphaLabel);
    152             }
    153         }
    154     }
    155 
    156     /**
    157      * Replaces one of a block's successors with a different label. Constructs
    158      * an updated BasicBlock instance and places it in {@code newBlocks}.
    159      *
    160      * @param block block to replace
    161      * @param oldLabel label of successor to replace
    162      * @param newLabel label of new successor
    163      */
    164     private void replaceSucc(BasicBlock block, int oldLabel, int newLabel) {
    165         IntList newSuccessors = block.getSuccessors().mutableCopy();
    166         int newPrimarySuccessor;
    167 
    168         newSuccessors.set(newSuccessors.indexOf(oldLabel), newLabel);
    169         newPrimarySuccessor = block.getPrimarySuccessor();
    170 
    171         if (newPrimarySuccessor == oldLabel) {
    172             newPrimarySuccessor = newLabel;
    173         }
    174 
    175         newSuccessors.setImmutable();
    176 
    177         BasicBlock newBB = new BasicBlock(block.getLabel(),
    178                 block.getInsns(), newSuccessors, newPrimarySuccessor);
    179 
    180         newBlocks.set(newBlocks.indexOfLabel(block.getLabel()), newBB);
    181     }
    182 }
    183