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.rop.code;
18
19import com.android.dx.util.Bits;
20import com.android.dx.util.Hex;
21import com.android.dx.util.IntList;
22
23/**
24 * All of the parts that make up a method at the rop layer.
25 */
26public final class RopMethod {
27    /** {@code non-null;} basic block list of the method */
28    private final BasicBlockList blocks;
29
30    /** {@code >= 0;} label for the block which starts the method */
31    private final int firstLabel;
32
33    /**
34     * {@code null-ok;} array of predecessors for each block, indexed by block
35     * label
36     */
37    private IntList[] predecessors;
38
39    /**
40     * {@code null-ok;} the predecessors for the implicit "exit" block, that is
41     * the labels for the blocks that return, if calculated
42     */
43    private IntList exitPredecessors;
44
45    /**
46     * Constructs an instance.
47     *
48     * @param blocks {@code non-null;} basic block list of the method
49     * @param firstLabel {@code >= 0;} the label of the first block to execute
50     */
51    public RopMethod(BasicBlockList blocks, int firstLabel) {
52        if (blocks == null) {
53            throw new NullPointerException("blocks == null");
54        }
55
56        if (firstLabel < 0) {
57            throw new IllegalArgumentException("firstLabel < 0");
58        }
59
60        this.blocks = blocks;
61        this.firstLabel = firstLabel;
62
63        this.predecessors = null;
64        this.exitPredecessors = null;
65    }
66
67    /**
68     * Gets the basic block list for this method.
69     *
70     * @return {@code non-null;} the list
71     */
72    public BasicBlockList getBlocks() {
73        return blocks;
74    }
75
76    /**
77     * Gets the label for the first block in the method that this list
78     * represents.
79     *
80     * @return {@code >= 0;} the first-block label
81     */
82    public int getFirstLabel() {
83        return firstLabel;
84    }
85
86    /**
87     * Gets the predecessors associated with the given block. This throws
88     * an exception if there is no block with the given label.
89     *
90     * @param label {@code >= 0;} the label of the block in question
91     * @return {@code non-null;} the predecessors of that block
92     */
93    public IntList labelToPredecessors(int label) {
94        if (exitPredecessors == null) {
95            calcPredecessors();
96        }
97
98        IntList result = predecessors[label];
99
100        if (result == null) {
101            throw new RuntimeException("no such block: " + Hex.u2(label));
102        }
103
104        return result;
105    }
106
107    /**
108     * Gets the exit predecessors for this instance.
109     *
110     * @return {@code non-null;} the exit predecessors
111     */
112    public IntList getExitPredecessors() {
113        if (exitPredecessors == null) {
114            calcPredecessors();
115        }
116
117        return exitPredecessors;
118    }
119
120
121    /**
122     * Returns an instance that is identical to this one, except that
123     * the registers in each instruction are offset by the given
124     * amount.
125     *
126     * @param delta the amount to offset register numbers by
127     * @return {@code non-null;} an appropriately-constructed instance
128     */
129    public RopMethod withRegisterOffset(int delta) {
130        RopMethod result = new RopMethod(blocks.withRegisterOffset(delta),
131                                         firstLabel);
132
133        if (exitPredecessors != null) {
134            /*
135             * The predecessors have been calculated. It's safe to
136             * inject these into the new instance, since the
137             * transformation being applied doesn't affect the
138             * predecessors.
139             */
140            result.exitPredecessors = exitPredecessors;
141            result.predecessors = predecessors;
142        }
143
144        return result;
145    }
146
147    /**
148     * Calculates the predecessor sets for each block as well as for the
149     * exit.
150     */
151    private void calcPredecessors() {
152        int maxLabel = blocks.getMaxLabel();
153        IntList[] predecessors = new IntList[maxLabel];
154        IntList exitPredecessors = new IntList(10);
155        int sz = blocks.size();
156
157        /*
158         * For each block, find its successors, and add the block's label to
159         * the successor's predecessors.
160         */
161        for (int i = 0; i < sz; i++) {
162            BasicBlock one = blocks.get(i);
163            int label = one.getLabel();
164            IntList successors = one.getSuccessors();
165            int ssz = successors.size();
166            if (ssz == 0) {
167                // This block exits.
168                exitPredecessors.add(label);
169            } else {
170                for (int j = 0; j < ssz; j++) {
171                    int succLabel = successors.get(j);
172                    IntList succPreds = predecessors[succLabel];
173                    if (succPreds == null) {
174                        succPreds = new IntList(10);
175                        predecessors[succLabel] = succPreds;
176                    }
177                    succPreds.add(label);
178                }
179            }
180        }
181
182        // Sort and immutablize all the predecessor lists.
183        for (int i = 0; i < maxLabel; i++) {
184            IntList preds = predecessors[i];
185            if (preds != null) {
186                preds.sort();
187                preds.setImmutable();
188            }
189        }
190
191        exitPredecessors.sort();
192        exitPredecessors.setImmutable();
193
194        /*
195         * The start label might not ever have had any predecessors
196         * added to it (probably doesn't, because of how Java gets
197         * translated into rop form). So, check for this and rectify
198         * the situation if required.
199         */
200        if (predecessors[firstLabel] == null) {
201            predecessors[firstLabel] = IntList.EMPTY;
202        }
203
204        this.predecessors = predecessors;
205        this.exitPredecessors = exitPredecessors;
206    }
207}
208