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
17package com.android.dx.ssa.back;
18
19import com.android.dx.rop.code.BasicBlock;
20import com.android.dx.rop.code.BasicBlockList;
21import com.android.dx.rop.code.CstInsn;
22import com.android.dx.rop.code.Insn;
23import com.android.dx.rop.code.InsnList;
24import com.android.dx.rop.code.RegOps;
25import com.android.dx.rop.code.RopMethod;
26import com.android.dx.rop.code.SwitchInsn;
27import com.android.dx.util.IntList;
28
29import 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 */
37public 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