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.dexgen.rop.code;
18
19import com.android.dexgen.rop.type.StdTypeList;
20import com.android.dexgen.rop.type.TypeList;
21import com.android.dexgen.util.Hex;
22import com.android.dexgen.util.IntList;
23import com.android.dexgen.util.LabeledList;
24
25/**
26 * List of {@link BasicBlock} instances.
27 */
28public 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    /**
152     * Gets the first block in the list with the given label, if any.
153     *
154     * @param label {@code >= 0;} the label to look for
155     * @return {@code non-null;} the so-labelled block
156     * @throws IllegalArgumentException thrown if the label isn't found
157     */
158    public BasicBlock labelToBlock(int label) {
159        int idx = indexOfLabel(label);
160
161        if (idx < 0) {
162            throw new IllegalArgumentException("no such label: "
163                    + Hex.u2(label));
164        }
165
166        return get(idx);
167    }
168
169    /**
170     * Visits each instruction of each block in the list, in order.
171     *
172     * @param visitor {@code non-null;} visitor to use
173     */
174    public void forEachInsn(Insn.Visitor visitor) {
175        int sz = size();
176
177        for (int i = 0; i < sz; i++) {
178            BasicBlock one = get(i);
179            InsnList insns = one.getInsns();
180            insns.forEach(visitor);
181        }
182    }
183
184    /**
185     * Returns an instance that is identical to this one, except that
186     * the registers in each instruction are offset by the given
187     * amount. Mutability of the result is inherited from the
188     * original.
189     *
190     * @param delta the amount to offset register numbers by
191     * @return {@code non-null;} an appropriately-constructed instance
192     */
193    public BasicBlockList withRegisterOffset(int delta) {
194        int sz = size();
195        BasicBlockList result = new BasicBlockList(sz);
196
197        for (int i = 0; i < sz; i++) {
198            BasicBlock one = (BasicBlock) get0(i);
199            if (one != null) {
200                result.set(i, one.withRegisterOffset(delta));
201            }
202        }
203
204        if (isImmutable()) {
205            result.setImmutable();
206        }
207
208        return result;
209    }
210
211    /**
212     * Returns a mutable copy of this list.
213     *
214     * @return {@code non-null;} an appropriately-constructed instance
215     */
216    public BasicBlockList getMutableCopy() {
217        return new BasicBlockList(this);
218    }
219
220    /**
221     * Gets the preferred successor for the given block. If the block
222     * only has one successor, then that is the preferred successor.
223     * Otherwise, if the block has a primay successor, then that is
224     * the preferred successor. If the block has no successors, then
225     * this returns {@code null}.
226     *
227     * @param block {@code non-null;} the block in question
228     * @return {@code null-ok;} the preferred successor, if any
229     */
230    public BasicBlock preferredSuccessorOf(BasicBlock block) {
231        int primarySuccessor = block.getPrimarySuccessor();
232        IntList successors = block.getSuccessors();
233        int succSize = successors.size();
234
235        switch (succSize) {
236            case 0: {
237                return null;
238            }
239            case 1: {
240                return labelToBlock(successors.get(0));
241            }
242        }
243
244        if (primarySuccessor != -1) {
245            return labelToBlock(primarySuccessor);
246        } else {
247            return labelToBlock(successors.get(0));
248        }
249    }
250
251    /**
252     * Compares the catches of two blocks for equality. This includes
253     * both the catch types and target labels.
254     *
255     * @param block1 {@code non-null;} one block to compare
256     * @param block2 {@code non-null;} the other block to compare
257     * @return {@code true} if the two blocks' non-primary successors
258     * are identical
259     */
260    public boolean catchesEqual(BasicBlock block1,
261            BasicBlock block2) {
262        TypeList catches1 = block1.getExceptionHandlerTypes();
263        TypeList catches2 = block2.getExceptionHandlerTypes();
264
265        if (!StdTypeList.equalContents(catches1, catches2)) {
266            return false;
267        }
268
269        IntList succ1 = block1.getSuccessors();
270        IntList succ2 = block2.getSuccessors();
271        int size = succ1.size(); // Both are guaranteed to be the same size.
272
273        int primary1 = block1.getPrimarySuccessor();
274        int primary2 = block2.getPrimarySuccessor();
275
276        if (((primary1 == -1) || (primary2 == -1))
277                && (primary1 != primary2)) {
278            /*
279             * For the current purpose, both blocks in question must
280             * either both have a primary or both not have a primary to
281             * be considered equal, and it turns out here that that's not
282             * the case.
283             */
284            return false;
285        }
286
287        for (int i = 0; i < size; i++) {
288            int label1 = succ1.get(i);
289            int label2 = succ2.get(i);
290
291            if (label1 == primary1) {
292                /*
293                 * It should be the case that block2's primary is at the
294                 * same index. If not, we consider the blocks unequal for
295                 * the current purpose.
296                 */
297                if (label2 != primary2) {
298                    return false;
299                }
300                continue;
301            }
302
303            if (label1 != label2) {
304                return false;
305            }
306        }
307
308        return true;
309    }
310
311    /**
312     * Instruction visitor class for counting registers used.
313     */
314    private static class RegCountVisitor
315            implements Insn.Visitor {
316        /** {@code >= 0;} register count in-progress */
317        private int regCount;
318
319        /**
320         * Constructs an instance.
321         */
322        public RegCountVisitor() {
323            regCount = 0;
324        }
325
326        /**
327         * Gets the register count.
328         *
329         * @return {@code >= 0;} the count
330         */
331        public int getRegCount() {
332            return regCount;
333        }
334
335        /** {@inheritDoc} */
336        public void visitPlainInsn(PlainInsn insn) {
337            visit(insn);
338        }
339
340        /** {@inheritDoc} */
341        public void visitPlainCstInsn(PlainCstInsn insn) {
342            visit(insn);
343        }
344
345        /** {@inheritDoc} */
346        public void visitSwitchInsn(SwitchInsn insn) {
347            visit(insn);
348        }
349
350        /** {@inheritDoc} */
351        public void visitThrowingCstInsn(ThrowingCstInsn insn) {
352            visit(insn);
353        }
354
355        /** {@inheritDoc} */
356        public void visitThrowingInsn(ThrowingInsn insn) {
357            visit(insn);
358        }
359
360        /** {@inheritDoc} */
361        public void visitFillArrayDataInsn(FillArrayDataInsn insn) {
362            visit(insn);
363        }
364
365        /**
366         * Helper for all the {@code visit*} methods.
367         *
368         * @param insn {@code non-null;} instruction being visited
369         */
370        private void visit(Insn insn) {
371            RegisterSpec result = insn.getResult();
372
373            if (result != null) {
374                processReg(result);
375            }
376
377            RegisterSpecList sources = insn.getSources();
378            int sz = sources.size();
379
380            for (int i = 0; i < sz; i++) {
381                processReg(sources.get(i));
382            }
383        }
384
385        /**
386         * Processes the given register spec.
387         *
388         * @param spec {@code non-null;} the register spec
389         */
390        private void processReg(RegisterSpec spec) {
391            int reg = spec.getNextReg();
392
393            if (reg > regCount) {
394                regCount = reg;
395            }
396        }
397    }
398}
399