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