Gitiles
Code Review Sign In
review.blissroms.org / platform_art / 71fe267165765bee6ff1b2e6c35de17910a14f80 / . / src / compiler / dex / mir_dataflow.cc
blob: add5ca0a821591d6166468aed76d2cce18d92ae8 [file] [log] [blame]
buzbee311ca162013-02-28 15:56:43 -0800[diff] [blame]1/*
2 * Copyright (C) 2011 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#include "compiler_internals.h"
18#include "local_value_numbering.h"
19#include "dataflow_iterator.h"
20
21namespace art {
22
23/*
24 * Main table containing data flow attributes for each bytecode. The
25 * first kNumPackedOpcodes entries are for Dalvik bytecode
26 * instructions, where extended opcode at the MIR level are appended
27 * afterwards.
28 *
29 * TODO - many optimization flags are incomplete - they will only limit the
30 * scope of optimizations but will not cause mis-optimizations.
31 */
32const int oat_data_flow_attributes[kMirOpLast] = {
33 // 00 NOP
34 DF_NOP,
35
36 // 01 MOVE vA, vB
37 DF_DA | DF_UB | DF_IS_MOVE,
38
39 // 02 MOVE_FROM16 vAA, vBBBB
40 DF_DA | DF_UB | DF_IS_MOVE,
41
42 // 03 MOVE_16 vAAAA, vBBBB
43 DF_DA | DF_UB | DF_IS_MOVE,
44
45 // 04 MOVE_WIDE vA, vB
46 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE,
47
48 // 05 MOVE_WIDE_FROM16 vAA, vBBBB
49 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE,
50
51 // 06 MOVE_WIDE_16 vAAAA, vBBBB
52 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_IS_MOVE,
53
54 // 07 MOVE_OBJECT vA, vB
55 DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B,
56
57 // 08 MOVE_OBJECT_FROM16 vAA, vBBBB
58 DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B,
59
60 // 09 MOVE_OBJECT_16 vAAAA, vBBBB
61 DF_DA | DF_UB | DF_NULL_TRANSFER_0 | DF_IS_MOVE | DF_REF_A | DF_REF_B,
62
63 // 0A MOVE_RESULT vAA
64 DF_DA,
65
66 // 0B MOVE_RESULT_WIDE vAA
67 DF_DA | DF_A_WIDE,
68
69 // 0C MOVE_RESULT_OBJECT vAA
70 DF_DA | DF_REF_A,
71
72 // 0D MOVE_EXCEPTION vAA
73 DF_DA | DF_REF_A,
74
75 // 0E RETURN_VOID
76 DF_NOP,
77
78 // 0F RETURN vAA
79 DF_UA,
80
81 // 10 RETURN_WIDE vAA
82 DF_UA | DF_A_WIDE,
83
84 // 11 RETURN_OBJECT vAA
85 DF_UA | DF_REF_A,
86
87 // 12 CONST_4 vA, #+B
88 DF_DA | DF_SETS_CONST,
89
90 // 13 CONST_16 vAA, #+BBBB
91 DF_DA | DF_SETS_CONST,
92
93 // 14 CONST vAA, #+BBBBBBBB
94 DF_DA | DF_SETS_CONST,
95
96 // 15 CONST_HIGH16 VAA, #+BBBB0000
97 DF_DA | DF_SETS_CONST,
98
99 // 16 CONST_WIDE_16 vAA, #+BBBB
100 DF_DA | DF_A_WIDE | DF_SETS_CONST,
101
102 // 17 CONST_WIDE_32 vAA, #+BBBBBBBB
103 DF_DA | DF_A_WIDE | DF_SETS_CONST,
104
105 // 18 CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB
106 DF_DA | DF_A_WIDE | DF_SETS_CONST,
107
108 // 19 CONST_WIDE_HIGH16 vAA, #+BBBB000000000000
109 DF_DA | DF_A_WIDE | DF_SETS_CONST,
110
111 // 1A CONST_STRING vAA, string@BBBB
112 DF_DA | DF_REF_A,
113
114 // 1B CONST_STRING_JUMBO vAA, string@BBBBBBBB
115 DF_DA | DF_REF_A,
116
117 // 1C CONST_CLASS vAA, type@BBBB
118 DF_DA | DF_REF_A,
119
120 // 1D MONITOR_ENTER vAA
121 DF_UA | DF_NULL_CHK_0 | DF_REF_A,
122
123 // 1E MONITOR_EXIT vAA
124 DF_UA | DF_NULL_CHK_0 | DF_REF_A,
125
126 // 1F CHK_CAST vAA, type@BBBB
127 DF_UA | DF_REF_A | DF_UMS,
128
129 // 20 INSTANCE_OF vA, vB, type@CCCC
130 DF_DA | DF_UB | DF_CORE_A | DF_REF_B | DF_UMS,
131
132 // 21 ARRAY_LENGTH vA, vB
133 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_CORE_A | DF_REF_B,
134
135 // 22 NEW_INSTANCE vAA, type@BBBB
136 DF_DA | DF_NON_NULL_DST | DF_REF_A | DF_UMS,
137
138 // 23 NEW_ARRAY vA, vB, type@CCCC
139 DF_DA | DF_UB | DF_NON_NULL_DST | DF_REF_A | DF_CORE_B | DF_UMS,
140
141 // 24 FILLED_NEW_ARRAY {vD, vE, vF, vG, vA}
142 DF_FORMAT_35C | DF_NON_NULL_RET | DF_UMS,
143
144 // 25 FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB
145 DF_FORMAT_3RC | DF_NON_NULL_RET | DF_UMS,
146
147 // 26 FILL_ARRAY_DATA vAA, +BBBBBBBB
148 DF_UA | DF_REF_A | DF_UMS,
149
150 // 27 THROW vAA
151 DF_UA | DF_REF_A | DF_UMS,
152
153 // 28 GOTO
154 DF_NOP,
155
156 // 29 GOTO_16
157 DF_NOP,
158
159 // 2A GOTO_32
160 DF_NOP,
161
162 // 2B PACKED_SWITCH vAA, +BBBBBBBB
163 DF_UA,
164
165 // 2C SPARSE_SWITCH vAA, +BBBBBBBB
166 DF_UA,
167
168 // 2D CMPL_FLOAT vAA, vBB, vCC
169 DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A,
170
171 // 2E CMPG_FLOAT vAA, vBB, vCC
172 DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C | DF_CORE_A,
173
174 // 2F CMPL_DOUBLE vAA, vBB, vCC
175 DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A,
176
177 // 30 CMPG_DOUBLE vAA, vBB, vCC
178 DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_B | DF_FP_C | DF_CORE_A,
179
180 // 31 CMP_LONG vAA, vBB, vCC
181 DF_DA | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
182
183 // 32 IF_EQ vA, vB, +CCCC
184 DF_UA | DF_UB,
185
186 // 33 IF_NE vA, vB, +CCCC
187 DF_UA | DF_UB,
188
189 // 34 IF_LT vA, vB, +CCCC
190 DF_UA | DF_UB,
191
192 // 35 IF_GE vA, vB, +CCCC
193 DF_UA | DF_UB,
194
195 // 36 IF_GT vA, vB, +CCCC
196 DF_UA | DF_UB,
197
198 // 37 IF_LE vA, vB, +CCCC
199 DF_UA | DF_UB,
200
201 // 38 IF_EQZ vAA, +BBBB
202 DF_UA,
203
204 // 39 IF_NEZ vAA, +BBBB
205 DF_UA,
206
207 // 3A IF_LTZ vAA, +BBBB
208 DF_UA,
209
210 // 3B IF_GEZ vAA, +BBBB
211 DF_UA,
212
213 // 3C IF_GTZ vAA, +BBBB
214 DF_UA,
215
216 // 3D IF_LEZ vAA, +BBBB
217 DF_UA,
218
219 // 3E UNUSED_3E
220 DF_NOP,
221
222 // 3F UNUSED_3F
223 DF_NOP,
224
225 // 40 UNUSED_40
226 DF_NOP,
227
228 // 41 UNUSED_41
229 DF_NOP,
230
231 // 42 UNUSED_42
232 DF_NOP,
233
234 // 43 UNUSED_43
235 DF_NOP,
236
237 // 44 AGET vAA, vBB, vCC
238 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C,
239
240 // 45 AGET_WIDE vAA, vBB, vCC
241 DF_DA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C,
242
243 // 46 AGET_OBJECT vAA, vBB, vCC
244 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_A | DF_REF_B | DF_CORE_C,
245
246 // 47 AGET_BOOLEAN vAA, vBB, vCC
247 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C,
248
249 // 48 AGET_BYTE vAA, vBB, vCC
250 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C,
251
252 // 49 AGET_CHAR vAA, vBB, vCC
253 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C,
254
255 // 4A AGET_SHORT vAA, vBB, vCC
256 DF_DA | DF_UB | DF_UC | DF_NULL_CHK_0 | DF_RANGE_CHK_1 | DF_REF_B | DF_CORE_C,
257
258 // 4B APUT vAA, vBB, vCC
259 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C,
260
261 // 4C APUT_WIDE vAA, vBB, vCC
262 DF_UA | DF_A_WIDE | DF_UB | DF_UC | DF_NULL_CHK_2 | DF_RANGE_CHK_3 | DF_REF_B | DF_CORE_C,
263
264 // 4D APUT_OBJECT vAA, vBB, vCC
265 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_A | DF_REF_B | DF_CORE_C,
266
267 // 4E APUT_BOOLEAN vAA, vBB, vCC
268 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C,
269
270 // 4F APUT_BYTE vAA, vBB, vCC
271 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C,
272
273 // 50 APUT_CHAR vAA, vBB, vCC
274 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C,
275
276 // 51 APUT_SHORT vAA, vBB, vCC
277 DF_UA | DF_UB | DF_UC | DF_NULL_CHK_1 | DF_RANGE_CHK_2 | DF_REF_B | DF_CORE_C,
278
279 // 52 IGET vA, vB, field@CCCC
280 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
281
282 // 53 IGET_WIDE vA, vB, field@CCCC
283 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
284
285 // 54 IGET_OBJECT vA, vB, field@CCCC
286 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B,
287
288 // 55 IGET_BOOLEAN vA, vB, field@CCCC
289 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
290
291 // 56 IGET_BYTE vA, vB, field@CCCC
292 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
293
294 // 57 IGET_CHAR vA, vB, field@CCCC
295 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
296
297 // 58 IGET_SHORT vA, vB, field@CCCC
298 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
299
300 // 59 IPUT vA, vB, field@CCCC
301 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
302
303 // 5A IPUT_WIDE vA, vB, field@CCCC
304 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B,
305
306 // 5B IPUT_OBJECT vA, vB, field@CCCC
307 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B,
308
309 // 5C IPUT_BOOLEAN vA, vB, field@CCCC
310 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
311
312 // 5D IPUT_BYTE vA, vB, field@CCCC
313 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
314
315 // 5E IPUT_CHAR vA, vB, field@CCCC
316 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
317
318 // 5F IPUT_SHORT vA, vB, field@CCCC
319 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
320
321 // 60 SGET vAA, field@BBBB
322 DF_DA | DF_UMS,
323
324 // 61 SGET_WIDE vAA, field@BBBB
325 DF_DA | DF_A_WIDE | DF_UMS,
326
327 // 62 SGET_OBJECT vAA, field@BBBB
328 DF_DA | DF_REF_A | DF_UMS,
329
330 // 63 SGET_BOOLEAN vAA, field@BBBB
331 DF_DA | DF_UMS,
332
333 // 64 SGET_BYTE vAA, field@BBBB
334 DF_DA | DF_UMS,
335
336 // 65 SGET_CHAR vAA, field@BBBB
337 DF_DA | DF_UMS,
338
339 // 66 SGET_SHORT vAA, field@BBBB
340 DF_DA | DF_UMS,
341
342 // 67 SPUT vAA, field@BBBB
343 DF_UA | DF_UMS,
344
345 // 68 SPUT_WIDE vAA, field@BBBB
346 DF_UA | DF_A_WIDE | DF_UMS,
347
348 // 69 SPUT_OBJECT vAA, field@BBBB
349 DF_UA | DF_REF_A | DF_UMS,
350
351 // 6A SPUT_BOOLEAN vAA, field@BBBB
352 DF_UA | DF_UMS,
353
354 // 6B SPUT_BYTE vAA, field@BBBB
355 DF_UA | DF_UMS,
356
357 // 6C SPUT_CHAR vAA, field@BBBB
358 DF_UA | DF_UMS,
359
360 // 6D SPUT_SHORT vAA, field@BBBB
361 DF_UA | DF_UMS,
362
363 // 6E INVOKE_VIRTUAL {vD, vE, vF, vG, vA}
364 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS,
365
366 // 6F INVOKE_SUPER {vD, vE, vF, vG, vA}
367 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS,
368
369 // 70 INVOKE_DIRECT {vD, vE, vF, vG, vA}
370 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS,
371
372 // 71 INVOKE_STATIC {vD, vE, vF, vG, vA}
373 DF_FORMAT_35C | DF_UMS,
374
375 // 72 INVOKE_INTERFACE {vD, vE, vF, vG, vA}
376 DF_FORMAT_35C | DF_UMS,
377
378 // 73 UNUSED_73
379 DF_NOP,
380
381 // 74 INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN}
382 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS,
383
384 // 75 INVOKE_SUPER_RANGE {vCCCC .. vNNNN}
385 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS,
386
387 // 76 INVOKE_DIRECT_RANGE {vCCCC .. vNNNN}
388 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS,
389
390 // 77 INVOKE_STATIC_RANGE {vCCCC .. vNNNN}
391 DF_FORMAT_3RC | DF_UMS,
392
393 // 78 INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN}
394 DF_FORMAT_3RC | DF_UMS,
395
396 // 79 UNUSED_79
397 DF_NOP,
398
399 // 7A UNUSED_7A
400 DF_NOP,
401
402 // 7B NEG_INT vA, vB
403 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
404
405 // 7C NOT_INT vA, vB
406 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
407
408 // 7D NEG_LONG vA, vB
409 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
410
411 // 7E NOT_LONG vA, vB
412 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
413
414 // 7F NEG_FLOAT vA, vB
415 DF_DA | DF_UB | DF_FP_A | DF_FP_B,
416
417 // 80 NEG_DOUBLE vA, vB
418 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
419
420 // 81 INT_TO_LONG vA, vB
421 DF_DA | DF_A_WIDE | DF_UB | DF_CORE_A | DF_CORE_B,
422
423 // 82 INT_TO_FLOAT vA, vB
424 DF_DA | DF_UB | DF_FP_A | DF_CORE_B,
425
426 // 83 INT_TO_DOUBLE vA, vB
427 DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_CORE_B,
428
429 // 84 LONG_TO_INT vA, vB
430 DF_DA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
431
432 // 85 LONG_TO_FLOAT vA, vB
433 DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B,
434
435 // 86 LONG_TO_DOUBLE vA, vB
436 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_CORE_B,
437
438 // 87 FLOAT_TO_INT vA, vB
439 DF_DA | DF_UB | DF_FP_B | DF_CORE_A,
440
441 // 88 FLOAT_TO_LONG vA, vB
442 DF_DA | DF_A_WIDE | DF_UB | DF_FP_B | DF_CORE_A,
443
444 // 89 FLOAT_TO_DOUBLE vA, vB
445 DF_DA | DF_A_WIDE | DF_UB | DF_FP_A | DF_FP_B,
446
447 // 8A DOUBLE_TO_INT vA, vB
448 DF_DA | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A,
449
450 // 8B DOUBLE_TO_LONG vA, vB
451 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_B | DF_CORE_A,
452
453 // 8C DOUBLE_TO_FLOAT vA, vB
454 DF_DA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
455
456 // 8D INT_TO_BYTE vA, vB
457 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
458
459 // 8E INT_TO_CHAR vA, vB
460 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
461
462 // 8F INT_TO_SHORT vA, vB
463 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
464
465 // 90 ADD_INT vAA, vBB, vCC
466 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
467
468 // 91 SUB_INT vAA, vBB, vCC
469 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
470
471 // 92 MUL_INT vAA, vBB, vCC
472 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
473
474 // 93 DIV_INT vAA, vBB, vCC
475 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
476
477 // 94 REM_INT vAA, vBB, vCC
478 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
479
480 // 95 AND_INT vAA, vBB, vCC
481 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
482
483 // 96 OR_INT vAA, vBB, vCC
484 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
485
486 // 97 XOR_INT vAA, vBB, vCC
487 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
488
489 // 98 SHL_INT vAA, vBB, vCC
490 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
491
492 // 99 SHR_INT vAA, vBB, vCC
493 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
494
495 // 9A USHR_INT vAA, vBB, vCC
496 DF_DA | DF_UB | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
497
498 // 9B ADD_LONG vAA, vBB, vCC
499 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
500
501 // 9C SUB_LONG vAA, vBB, vCC
502 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
503
504 // 9D MUL_LONG vAA, vBB, vCC
505 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
506
507 // 9E DIV_LONG vAA, vBB, vCC
508 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
509
510 // 9F REM_LONG vAA, vBB, vCC
511 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
512
513 // A0 AND_LONG vAA, vBB, vCC
514 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
515
516 // A1 OR_LONG vAA, vBB, vCC
517 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
518
519 // A2 XOR_LONG vAA, vBB, vCC
520 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_CORE_A | DF_CORE_B | DF_CORE_C,
521
522 // A3 SHL_LONG vAA, vBB, vCC
523 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
524
525 // A4 SHR_LONG vAA, vBB, vCC
526 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
527
528 // A5 USHR_LONG vAA, vBB, vCC
529 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_CORE_A | DF_CORE_B | DF_CORE_C,
530
531 // A6 ADD_FLOAT vAA, vBB, vCC
532 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
533
534 // A7 SUB_FLOAT vAA, vBB, vCC
535 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
536
537 // A8 MUL_FLOAT vAA, vBB, vCC
538 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
539
540 // A9 DIV_FLOAT vAA, vBB, vCC
541 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
542
543 // AA REM_FLOAT vAA, vBB, vCC
544 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
545
546 // AB ADD_DOUBLE vAA, vBB, vCC
547 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
548
549 // AC SUB_DOUBLE vAA, vBB, vCC
550 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
551
552 // AD MUL_DOUBLE vAA, vBB, vCC
553 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
554
555 // AE DIV_DOUBLE vAA, vBB, vCC
556 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
557
558 // AF REM_DOUBLE vAA, vBB, vCC
559 DF_DA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_UC | DF_C_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
560
561 // B0 ADD_INT_2ADDR vA, vB
562 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
563
564 // B1 SUB_INT_2ADDR vA, vB
565 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
566
567 // B2 MUL_INT_2ADDR vA, vB
568 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
569
570 // B3 DIV_INT_2ADDR vA, vB
571 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
572
573 // B4 REM_INT_2ADDR vA, vB
574 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
575
576 // B5 AND_INT_2ADDR vA, vB
577 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
578
579 // B6 OR_INT_2ADDR vA, vB
580 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
581
582 // B7 XOR_INT_2ADDR vA, vB
583 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
584
585 // B8 SHL_INT_2ADDR vA, vB
586 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
587
588 // B9 SHR_INT_2ADDR vA, vB
589 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
590
591 // BA USHR_INT_2ADDR vA, vB
592 DF_DA | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
593
594 // BB ADD_LONG_2ADDR vA, vB
595 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
596
597 // BC SUB_LONG_2ADDR vA, vB
598 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
599
600 // BD MUL_LONG_2ADDR vA, vB
601 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
602
603 // BE DIV_LONG_2ADDR vA, vB
604 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
605
606 // BF REM_LONG_2ADDR vA, vB
607 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
608
609 // C0 AND_LONG_2ADDR vA, vB
610 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
611
612 // C1 OR_LONG_2ADDR vA, vB
613 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
614
615 // C2 XOR_LONG_2ADDR vA, vB
616 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
617
618 // C3 SHL_LONG_2ADDR vA, vB
619 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
620
621 // C4 SHR_LONG_2ADDR vA, vB
622 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
623
624 // C5 USHR_LONG_2ADDR vA, vB
625 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_CORE_A | DF_CORE_B,
626
627 // C6 ADD_FLOAT_2ADDR vA, vB
628 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
629
630 // C7 SUB_FLOAT_2ADDR vA, vB
631 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
632
633 // C8 MUL_FLOAT_2ADDR vA, vB
634 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
635
636 // C9 DIV_FLOAT_2ADDR vA, vB
637 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
638
639 // CA REM_FLOAT_2ADDR vA, vB
640 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
641
642 // CB ADD_DOUBLE_2ADDR vA, vB
643 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
644
645 // CC SUB_DOUBLE_2ADDR vA, vB
646 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
647
648 // CD MUL_DOUBLE_2ADDR vA, vB
649 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
650
651 // CE DIV_DOUBLE_2ADDR vA, vB
652 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
653
654 // CF REM_DOUBLE_2ADDR vA, vB
655 DF_DA | DF_A_WIDE | DF_UA | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
656
657 // D0 ADD_INT_LIT16 vA, vB, #+CCCC
658 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
659
660 // D1 RSUB_INT vA, vB, #+CCCC
661 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
662
663 // D2 MUL_INT_LIT16 vA, vB, #+CCCC
664 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
665
666 // D3 DIV_INT_LIT16 vA, vB, #+CCCC
667 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
668
669 // D4 REM_INT_LIT16 vA, vB, #+CCCC
670 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
671
672 // D5 AND_INT_LIT16 vA, vB, #+CCCC
673 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
674
675 // D6 OR_INT_LIT16 vA, vB, #+CCCC
676 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
677
678 // D7 XOR_INT_LIT16 vA, vB, #+CCCC
679 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
680
681 // D8 ADD_INT_LIT8 vAA, vBB, #+CC
682 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
683
684 // D9 RSUB_INT_LIT8 vAA, vBB, #+CC
685 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
686
687 // DA MUL_INT_LIT8 vAA, vBB, #+CC
688 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
689
690 // DB DIV_INT_LIT8 vAA, vBB, #+CC
691 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
692
693 // DC REM_INT_LIT8 vAA, vBB, #+CC
694 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
695
696 // DD AND_INT_LIT8 vAA, vBB, #+CC
697 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
698
699 // DE OR_INT_LIT8 vAA, vBB, #+CC
700 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
701
702 // DF XOR_INT_LIT8 vAA, vBB, #+CC
703 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
704
705 // E0 SHL_INT_LIT8 vAA, vBB, #+CC
706 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
707
708 // E1 SHR_INT_LIT8 vAA, vBB, #+CC
709 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
710
711 // E2 USHR_INT_LIT8 vAA, vBB, #+CC
712 DF_DA | DF_UB | DF_CORE_A | DF_CORE_B,
713
714 // E3 IGET_VOLATILE
715 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
716
717 // E4 IPUT_VOLATILE
718 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_B,
719
720 // E5 SGET_VOLATILE
721 DF_DA | DF_UMS,
722
723 // E6 SPUT_VOLATILE
724 DF_UA | DF_UMS,
725
726 // E7 IGET_OBJECT_VOLATILE
727 DF_DA | DF_UB | DF_NULL_CHK_0 | DF_REF_A | DF_REF_B,
728
729 // E8 IGET_WIDE_VOLATILE
730 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0 | DF_REF_B,
731
732 // E9 IPUT_WIDE_VOLATILE
733 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2 | DF_REF_B,
734
735 // EA SGET_WIDE_VOLATILE
736 DF_DA | DF_A_WIDE | DF_UMS,
737
738 // EB SPUT_WIDE_VOLATILE
739 DF_UA | DF_A_WIDE | DF_UMS,
740
741 // EC BREAKPOINT
742 DF_NOP,
743
744 // ED THROW_VERIFICATION_ERROR
745 DF_NOP | DF_UMS,
746
747 // EE EXECUTE_INLINE
748 DF_FORMAT_35C,
749
750 // EF EXECUTE_INLINE_RANGE
751 DF_FORMAT_3RC,
752
753 // F0 INVOKE_OBJECT_INIT_RANGE
754 DF_NOP | DF_NULL_CHK_0,
755
756 // F1 RETURN_VOID_BARRIER
757 DF_NOP,
758
759 // F2 IGET_QUICK
760 DF_DA | DF_UB | DF_NULL_CHK_0,
761
762 // F3 IGET_WIDE_QUICK
763 DF_DA | DF_A_WIDE | DF_UB | DF_NULL_CHK_0,
764
765 // F4 IGET_OBJECT_QUICK
766 DF_DA | DF_UB | DF_NULL_CHK_0,
767
768 // F5 IPUT_QUICK
769 DF_UA | DF_UB | DF_NULL_CHK_1,
770
771 // F6 IPUT_WIDE_QUICK
772 DF_UA | DF_A_WIDE | DF_UB | DF_NULL_CHK_2,
773
774 // F7 IPUT_OBJECT_QUICK
775 DF_UA | DF_UB | DF_NULL_CHK_1,
776
777 // F8 INVOKE_VIRTUAL_QUICK
778 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS,
779
780 // F9 INVOKE_VIRTUAL_QUICK_RANGE
781 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS,
782
783 // FA INVOKE_SUPER_QUICK
784 DF_FORMAT_35C | DF_NULL_CHK_OUT0 | DF_UMS,
785
786 // FB INVOKE_SUPER_QUICK_RANGE
787 DF_FORMAT_3RC | DF_NULL_CHK_OUT0 | DF_UMS,
788
789 // FC IPUT_OBJECT_VOLATILE
790 DF_UA | DF_UB | DF_NULL_CHK_1 | DF_REF_A | DF_REF_B,
791
792 // FD SGET_OBJECT_VOLATILE
793 DF_DA | DF_REF_A | DF_UMS,
794
795 // FE SPUT_OBJECT_VOLATILE
796 DF_UA | DF_REF_A | DF_UMS,
797
798 // FF UNUSED_FF
799 DF_NOP,
800
801 // Beginning of extended MIR opcodes
802 // 100 MIR_PHI
803 DF_DA | DF_NULL_TRANSFER_N,
804
805 // 101 MIR_COPY
806 DF_DA | DF_UB | DF_IS_MOVE,
807
808 // 102 MIR_FUSED_CMPL_FLOAT
809 DF_UA | DF_UB | DF_FP_A | DF_FP_B,
810
811 // 103 MIR_FUSED_CMPG_FLOAT
812 DF_UA | DF_UB | DF_FP_A | DF_FP_B,
813
814 // 104 MIR_FUSED_CMPL_DOUBLE
815 DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
816
817 // 105 MIR_FUSED_CMPG_DOUBLE
818 DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_FP_A | DF_FP_B,
819
820 // 106 MIR_FUSED_CMP_LONG
821 DF_UA | DF_A_WIDE | DF_UB | DF_B_WIDE | DF_CORE_A | DF_CORE_B,
822
823 // 107 MIR_NOP
824 DF_NOP,
825
826 // 108 MIR_NULL_CHECK
827 0,
828
829 // 109 MIR_RANGE_CHECK
830 0,
831
832 // 110 MIR_DIV_ZERO_CHECK
833 0,
834
835 // 111 MIR_CHECK
836 0,
837
838 // 112 MIR_CHECKPART2
839 0,
840
841 // 113 MIR_SELECT
842 DF_DA | DF_UB,
843};
844
845/* Return the base virtual register for a SSA name */
Ian Rogers71fe2672013-03-19 20:45:02 -0700[diff] [blame^]846int MIRGraph::SRegToVReg(int ssa_reg) const {
buzbee311ca162013-02-28 15:56:43 -0800[diff] [blame]847 DCHECK_LT(ssa_reg, static_cast<int>(ssa_base_vregs_->num_used));
848 return GET_ELEM_N(ssa_base_vregs_, int, ssa_reg);
849}
850
851/* Any register that is used before being defined is considered live-in */
852void MIRGraph::HandleLiveInUse(ArenaBitVector* use_v, ArenaBitVector* def_v,
853 ArenaBitVector* live_in_v, int dalvik_reg_id)
854{
855 SetBit(cu_, use_v, dalvik_reg_id);
856 if (!IsBitSet(def_v, dalvik_reg_id)) {
857 SetBit(cu_, live_in_v, dalvik_reg_id);
858 }
859}
860
861/* Mark a reg as being defined */
862void MIRGraph::HandleDef(ArenaBitVector* def_v, int dalvik_reg_id)
863{
864 SetBit(cu_, def_v, dalvik_reg_id);
865}
866
867/*
868 * Find out live-in variables for natural loops. Variables that are live-in in
869 * the main loop body are considered to be defined in the entry block.
870 */
871bool MIRGraph::FindLocalLiveIn(BasicBlock* bb)
872{
873 MIR* mir;
874 ArenaBitVector *use_v, *def_v, *live_in_v;
875
876 if (bb->data_flow_info == NULL) return false;
877
878 use_v = bb->data_flow_info->use_v =
879 AllocBitVector(cu_, cu_->num_dalvik_registers, false, kBitMapUse);
880 def_v = bb->data_flow_info->def_v =
881 AllocBitVector(cu_, cu_->num_dalvik_registers, false, kBitMapDef);
882 live_in_v = bb->data_flow_info->live_in_v =
883 AllocBitVector(cu_, cu_->num_dalvik_registers, false, kBitMapLiveIn);
884
885 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
886 int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
887 DecodedInstruction *d_insn = &mir->dalvikInsn;
888
889 if (df_attributes & DF_HAS_USES) {
890 if (df_attributes & DF_UA) {
891 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vA);
892 if (df_attributes & DF_A_WIDE) {
893 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vA+1);
894 }
895 }
896 if (df_attributes & DF_UB) {
897 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vB);
898 if (df_attributes & DF_B_WIDE) {
899 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vB+1);
900 }
901 }
902 if (df_attributes & DF_UC) {
903 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC);
904 if (df_attributes & DF_C_WIDE) {
905 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC+1);
906 }
907 }
908 }
909 if (df_attributes & DF_FORMAT_35C) {
910 for (unsigned int i = 0; i < d_insn->vA; i++) {
911 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->arg[i]);
912 }
913 }
914 if (df_attributes & DF_FORMAT_3RC) {
915 for (unsigned int i = 0; i < d_insn->vA; i++) {
916 HandleLiveInUse(use_v, def_v, live_in_v, d_insn->vC+i);
917 }
918 }
919 if (df_attributes & DF_HAS_DEFS) {
920 HandleDef(def_v, d_insn->vA);
921 if (df_attributes & DF_A_WIDE) {
922 HandleDef(def_v, d_insn->vA+1);
923 }
924 }
925 }
926 return true;
927}
928
929int MIRGraph::AddNewSReg(int v_reg)
930{
931 // Compiler temps always have a subscript of 0
932 int subscript = (v_reg < 0) ? 0 : ++ssa_last_defs_[v_reg];
933 int ssa_reg = GetNumSSARegs();
934 SetNumSSARegs(ssa_reg + 1);
935 InsertGrowableList(cu_, ssa_base_vregs_, v_reg);
936 InsertGrowableList(cu_, ssa_subscripts_, subscript);
937 std::string ssa_name = GetSSAName(cu_, ssa_reg);
938 char* name = static_cast<char*>(NewMem(cu_, ssa_name.length() + 1, false, kAllocDFInfo));
939 strncpy(name, ssa_name.c_str(), ssa_name.length() + 1);
940 InsertGrowableList(cu_, ssa_strings_, reinterpret_cast<uintptr_t>(name));
941 DCHECK_EQ(ssa_base_vregs_->num_used, ssa_subscripts_->num_used);
942 return ssa_reg;
943}
944
945/* Find out the latest SSA register for a given Dalvik register */
946void MIRGraph::HandleSSAUse(int* uses, int dalvik_reg, int reg_index)
947{
948 DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu_->num_dalvik_registers));
949 uses[reg_index] = vreg_to_ssa_map_[dalvik_reg];
950}
951
952/* Setup a new SSA register for a given Dalvik register */
953void MIRGraph::HandleSSADef(int* defs, int dalvik_reg, int reg_index)
954{
955 DCHECK((dalvik_reg >= 0) && (dalvik_reg < cu_->num_dalvik_registers));
956 int ssa_reg = AddNewSReg(dalvik_reg);
957 vreg_to_ssa_map_[dalvik_reg] = ssa_reg;
958 defs[reg_index] = ssa_reg;
959}
960
961/* Look up new SSA names for format_35c instructions */
962void MIRGraph::DataFlowSSAFormat35C(MIR* mir)
963{
964 DecodedInstruction *d_insn = &mir->dalvikInsn;
965 int num_uses = d_insn->vA;
966 int i;
967
968 mir->ssa_rep->num_uses = num_uses;
969 mir->ssa_rep->uses = static_cast<int*>(NewMem(cu_, sizeof(int) * num_uses, true, kAllocDFInfo));
970 // NOTE: will be filled in during type & size inference pass
971 mir->ssa_rep->fp_use = static_cast<bool*>(NewMem(cu_, sizeof(bool) * num_uses, true,
972 kAllocDFInfo));
973
974 for (i = 0; i < num_uses; i++) {
975 HandleSSAUse(mir->ssa_rep->uses, d_insn->arg[i], i);
976 }
977}
978
979/* Look up new SSA names for format_3rc instructions */
980void MIRGraph::DataFlowSSAFormat3RC(MIR* mir)
981{
982 DecodedInstruction *d_insn = &mir->dalvikInsn;
983 int num_uses = d_insn->vA;
984 int i;
985
986 mir->ssa_rep->num_uses = num_uses;
987 mir->ssa_rep->uses = static_cast<int*>(NewMem(cu_, sizeof(int) * num_uses, true, kAllocDFInfo));
988 // NOTE: will be filled in during type & size inference pass
989 mir->ssa_rep->fp_use = static_cast<bool*>(NewMem(cu_, sizeof(bool) * num_uses, true,
990 kAllocDFInfo));
991
992 for (i = 0; i < num_uses; i++) {
993 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC+i, i);
994 }
995}
996
997/* Entry function to convert a block into SSA representation */
998bool MIRGraph::DoSSAConversion(BasicBlock* bb)
999{
1000 MIR* mir;
1001
1002 if (bb->data_flow_info == NULL) return false;
1003
1004 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
1005 mir->ssa_rep = static_cast<struct SSARepresentation *>(NewMem(cu_, sizeof(SSARepresentation),
1006 true, kAllocDFInfo));
1007
1008 int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
1009
1010 // If not a pseudo-op, note non-leaf or can throw
1011 if (static_cast<int>(mir->dalvikInsn.opcode) <
1012 static_cast<int>(kNumPackedOpcodes)) {
1013 int flags = Instruction::FlagsOf(mir->dalvikInsn.opcode);
1014
1015 if (flags & Instruction::kInvoke) {
1016 cu_->attributes &= ~METHOD_IS_LEAF;
1017 }
1018 }
1019
1020 int num_uses = 0;
1021
1022 if (df_attributes & DF_FORMAT_35C) {
1023 DataFlowSSAFormat35C(mir);
1024 continue;
1025 }
1026
1027 if (df_attributes & DF_FORMAT_3RC) {
1028 DataFlowSSAFormat3RC(mir);
1029 continue;
1030 }
1031
1032 if (df_attributes & DF_HAS_USES) {
1033 if (df_attributes & DF_UA) {
1034 num_uses++;
1035 if (df_attributes & DF_A_WIDE) {
1036 num_uses ++;
1037 }
1038 }
1039 if (df_attributes & DF_UB) {
1040 num_uses++;
1041 if (df_attributes & DF_B_WIDE) {
1042 num_uses ++;
1043 }
1044 }
1045 if (df_attributes & DF_UC) {
1046 num_uses++;
1047 if (df_attributes & DF_C_WIDE) {
1048 num_uses ++;
1049 }
1050 }
1051 }
1052
1053 if (num_uses) {
1054 mir->ssa_rep->num_uses = num_uses;
1055 mir->ssa_rep->uses = static_cast<int*>(NewMem(cu_, sizeof(int) * num_uses, false,
1056 kAllocDFInfo));
1057 mir->ssa_rep->fp_use = static_cast<bool*>(NewMem(cu_, sizeof(bool) * num_uses, false,
1058 kAllocDFInfo));
1059 }
1060
1061 int num_defs = 0;
1062
1063 if (df_attributes & DF_HAS_DEFS) {
1064 num_defs++;
1065 if (df_attributes & DF_A_WIDE) {
1066 num_defs++;
1067 }
1068 }
1069
1070 if (num_defs) {
1071 mir->ssa_rep->num_defs = num_defs;
1072 mir->ssa_rep->defs = static_cast<int*>(NewMem(cu_, sizeof(int) * num_defs, false,
1073 kAllocDFInfo));
1074 mir->ssa_rep->fp_def = static_cast<bool*>(NewMem(cu_, sizeof(bool) * num_defs, false,
1075 kAllocDFInfo));
1076 }
1077
1078 DecodedInstruction *d_insn = &mir->dalvikInsn;
1079
1080 if (df_attributes & DF_HAS_USES) {
1081 num_uses = 0;
1082 if (df_attributes & DF_UA) {
1083 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A;
1084 HandleSSAUse(mir->ssa_rep->uses, d_insn->vA, num_uses++);
1085 if (df_attributes & DF_A_WIDE) {
1086 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_A;
1087 HandleSSAUse(mir->ssa_rep->uses, d_insn->vA+1, num_uses++);
1088 }
1089 }
1090 if (df_attributes & DF_UB) {
1091 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B;
1092 HandleSSAUse(mir->ssa_rep->uses, d_insn->vB, num_uses++);
1093 if (df_attributes & DF_B_WIDE) {
1094 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_B;
1095 HandleSSAUse(mir->ssa_rep->uses, d_insn->vB+1, num_uses++);
1096 }
1097 }
1098 if (df_attributes & DF_UC) {
1099 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C;
1100 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC, num_uses++);
1101 if (df_attributes & DF_C_WIDE) {
1102 mir->ssa_rep->fp_use[num_uses] = df_attributes & DF_FP_C;
1103 HandleSSAUse(mir->ssa_rep->uses, d_insn->vC+1, num_uses++);
1104 }
1105 }
1106 }
1107 if (df_attributes & DF_HAS_DEFS) {
1108 mir->ssa_rep->fp_def[0] = df_attributes & DF_FP_A;
1109 HandleSSADef(mir->ssa_rep->defs, d_insn->vA, 0);
1110 if (df_attributes & DF_A_WIDE) {
1111 mir->ssa_rep->fp_def[1] = df_attributes & DF_FP_A;
1112 HandleSSADef(mir->ssa_rep->defs, d_insn->vA+1, 1);
1113 }
1114 }
1115 }
1116
1117 if (!cu_->disable_dataflow) {
1118 /*
1119 * Take a snapshot of Dalvik->SSA mapping at the end of each block. The
1120 * input to PHI nodes can be derived from the snapshot of all
1121 * predecessor blocks.
1122 */
1123 bb->data_flow_info->vreg_to_ssa_map =
1124 static_cast<int*>(NewMem(cu_, sizeof(int) * cu_->num_dalvik_registers, false,
1125 kAllocDFInfo));
1126
1127 memcpy(bb->data_flow_info->vreg_to_ssa_map, vreg_to_ssa_map_,
1128 sizeof(int) * cu_->num_dalvik_registers);
1129 }
1130 return true;
1131}
1132
1133/* Setup the basic data structures for SSA conversion */
1134void MIRGraph::CompilerInitializeSSAConversion()
1135{
1136 int i;
1137 int num_dalvik_reg = cu_->num_dalvik_registers;
1138
1139 ssa_base_vregs_ =
1140 static_cast<GrowableList*>(NewMem(cu_, sizeof(GrowableList), false, kAllocDFInfo));
1141 ssa_subscripts_ =
1142 static_cast<GrowableList*>(NewMem(cu_, sizeof(GrowableList), false, kAllocDFInfo));
1143 ssa_strings_ =
1144 static_cast<GrowableList*>(NewMem(cu_, sizeof(GrowableList), false, kAllocDFInfo));
1145 // Create the ssa mappings, estimating the max size
1146 CompilerInitGrowableList(cu_, ssa_base_vregs_, num_dalvik_reg + GetDefCount() + 128,
1147 kListSSAtoDalvikMap);
1148 CompilerInitGrowableList(cu_, ssa_subscripts_, num_dalvik_reg + GetDefCount() + 128,
1149 kListSSAtoDalvikMap);
1150 CompilerInitGrowableList(cu_, ssa_strings_, num_dalvik_reg + GetDefCount() + 128,
1151 kListSSAtoDalvikMap);
1152 /*
1153 * Initial number of SSA registers is equal to the number of Dalvik
1154 * registers.
1155 */
1156 SetNumSSARegs(num_dalvik_reg);
1157
1158 /*
1159 * Initialize the SSA2Dalvik map list. For the first num_dalvik_reg elements,
1160 * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value
1161 * into "(0 << 16) | i"
1162 */
1163 for (i = 0; i < num_dalvik_reg; i++) {
1164 InsertGrowableList(cu_, ssa_base_vregs_, i);
1165 InsertGrowableList(cu_, ssa_subscripts_, 0);
1166 std::string ssa_name = GetSSAName(cu_, i);
1167 char* name = static_cast<char*>(NewMem(cu_, ssa_name.length() + 1, true, kAllocDFInfo));
1168 strncpy(name, ssa_name.c_str(), ssa_name.length() + 1);
1169 InsertGrowableList(cu_, ssa_strings_, reinterpret_cast<uintptr_t>(name));
1170 }
1171
1172 /*
1173 * Initialize the DalvikToSSAMap map. There is one entry for each
1174 * Dalvik register, and the SSA names for those are the same.
1175 */
1176 vreg_to_ssa_map_ =
1177 static_cast<int*>(NewMem(cu_, sizeof(int) * num_dalvik_reg, false, kAllocDFInfo));
1178 /* Keep track of the higest def for each dalvik reg */
1179 ssa_last_defs_ =
1180 static_cast<int*>(NewMem(cu_, sizeof(int) * num_dalvik_reg, false, kAllocDFInfo));
1181
1182 for (i = 0; i < num_dalvik_reg; i++) {
1183 vreg_to_ssa_map_[i] = i;
1184 ssa_last_defs_[i] = 0;
1185 }
1186
1187 /* Add ssa reg for Method* */
1188 cu_->method_sreg = AddNewSReg(SSA_METHOD_BASEREG);
1189
1190 /*
1191 * Allocate the BasicBlockDataFlow structure for the entry and code blocks
1192 */
1193 GrowableListIterator iterator = GetBasicBlockIterator();
1194
1195 while (true) {
1196 BasicBlock* bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iterator));
1197 if (bb == NULL) break;
1198 if (bb->hidden == true) continue;
1199 if (bb->block_type == kDalvikByteCode ||
1200 bb->block_type == kEntryBlock ||
1201 bb->block_type == kExitBlock) {
1202 bb->data_flow_info = static_cast<BasicBlockDataFlow*>(NewMem(cu_, sizeof(BasicBlockDataFlow),
1203 true, kAllocDFInfo));
1204 }
1205 }
1206}
1207
1208/* Clear the visited flag for each BB */
1209bool MIRGraph::ClearVisitedFlag(struct BasicBlock* bb)
1210{
1211 bb->visited = false;
1212 return true;
1213}
1214
1215/*
1216 * This function will make a best guess at whether the invoke will
1217 * end up using Method*. It isn't critical to get it exactly right,
1218 * and attempting to do would involve more complexity than it's
1219 * worth.
1220 */
1221bool MIRGraph::InvokeUsesMethodStar(MIR* mir)
1222{
1223 InvokeType type;
1224 Instruction::Code opcode = mir->dalvikInsn.opcode;
1225 switch (opcode) {
1226 case Instruction::INVOKE_STATIC:
1227 case Instruction::INVOKE_STATIC_RANGE:
1228 type = kStatic;
1229 break;
1230 case Instruction::INVOKE_DIRECT:
1231 case Instruction::INVOKE_DIRECT_RANGE:
1232 type = kDirect;
1233 break;
1234 case Instruction::INVOKE_VIRTUAL:
1235 case Instruction::INVOKE_VIRTUAL_RANGE:
1236 type = kVirtual;
1237 break;
1238 case Instruction::INVOKE_INTERFACE:
1239 case Instruction::INVOKE_INTERFACE_RANGE:
1240 return false;
1241 case Instruction::INVOKE_SUPER_RANGE:
1242 case Instruction::INVOKE_SUPER:
1243 type = kSuper;
1244 break;
1245 default:
1246 LOG(WARNING) << "Unexpected invoke op: " << opcode;
1247 return false;
1248 }
1249 DexCompilationUnit m_unit(cu_);
1250 // TODO: add a flag so we don't counts the stats for this twice
1251 uint32_t dex_method_idx = mir->dalvikInsn.vB;
1252 int vtable_idx;
1253 uintptr_t direct_code;
1254 uintptr_t direct_method;
1255 bool fast_path =
1256 cu_->compiler_driver->ComputeInvokeInfo(dex_method_idx, &m_unit, type,
1257 vtable_idx, direct_code,
1258 direct_method) &&
1259 !(cu_->enable_debug & (1 << kDebugSlowInvokePath));
1260 return (((type == kDirect) || (type == kStatic)) &&
1261 fast_path && ((direct_code == 0) || (direct_method == 0)));
1262}
1263
1264/*
1265 * Count uses, weighting by loop nesting depth. This code only
1266 * counts explicitly used s_regs. A later phase will add implicit
1267 * counts for things such as Method*, null-checked references, etc.
1268 */
1269bool MIRGraph::CountUses(struct BasicBlock* bb)
1270{
1271 if (bb->block_type != kDalvikByteCode) {
1272 return false;
1273 }
1274 for (MIR* mir = bb->first_mir_insn; (mir != NULL); mir = mir->next) {
1275 if (mir->ssa_rep == NULL) {
1276 continue;
1277 }
1278 uint32_t weight = std::min(16U, static_cast<uint32_t>(bb->nesting_depth));
1279 for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
1280 int s_reg = mir->ssa_rep->uses[i];
1281 DCHECK_LT(s_reg, static_cast<int>(use_counts_.num_used));
1282 raw_use_counts_.elem_list[s_reg]++;
1283 use_counts_.elem_list[s_reg] += (1 << weight);
1284 }
1285 if (!(cu_->disable_opt & (1 << kPromoteCompilerTemps))) {
1286 int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
1287 // Implicit use of Method* ? */
1288 if (df_attributes & DF_UMS) {
1289 /*
1290 * Some invokes will not use Method* - need to perform test similar
1291 * to that found in GenInvoke() to decide whether to count refs
1292 * for Method* on invoke-class opcodes.
1293 * TODO: refactor for common test here, save results for GenInvoke
1294 */
1295 int uses_method_star = true;
1296 if ((df_attributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) &&
1297 !(df_attributes & DF_NON_NULL_RET)) {
1298 uses_method_star &= InvokeUsesMethodStar(mir);
1299 }
1300 if (uses_method_star) {
1301 raw_use_counts_.elem_list[cu_->method_sreg]++;
1302 use_counts_.elem_list[cu_->method_sreg] += (1 << weight);
1303 }
1304 }
1305 }
1306 }
1307 return false;
1308}
1309
1310void MIRGraph::MethodUseCount()
1311{
1312 int num_ssa_regs = GetNumSSARegs();
1313 CompilerInitGrowableList(cu_, &use_counts_, num_ssa_regs + 32, kListMisc);
1314 CompilerInitGrowableList(cu_, &raw_use_counts_, num_ssa_regs + 32, kListMisc);
1315 // Initialize list
1316 for (int i = 0; i < num_ssa_regs; i++) {
1317 InsertGrowableList(cu_, &use_counts_, 0);
1318 InsertGrowableList(cu_, &raw_use_counts_, 0);
1319 }
1320 if (cu_->disable_opt & (1 << kPromoteRegs)) {
1321 return;
1322 }
1323 DataflowIterator iter(this, kAllNodes, false /* not iterative */);
1324 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
1325 CountUses(bb);
1326 }
1327}
1328
1329/* Verify if all the successor is connected with all the claimed predecessors */
1330bool MIRGraph::VerifyPredInfo(BasicBlock* bb)
1331{
1332 GrowableListIterator iter;
1333
1334 GrowableListIteratorInit(bb->predecessors, &iter);
1335 while (true) {
1336 BasicBlock *pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter));
1337 if (!pred_bb) break;
1338 bool found = false;
1339 if (pred_bb->taken == bb) {
1340 found = true;
1341 } else if (pred_bb->fall_through == bb) {
1342 found = true;
1343 } else if (pred_bb->successor_block_list.block_list_type != kNotUsed) {
1344 GrowableListIterator iterator;
1345 GrowableListIteratorInit(&pred_bb->successor_block_list.blocks,
1346 &iterator);
1347 while (true) {
1348 SuccessorBlockInfo *successor_block_info =
1349 reinterpret_cast<SuccessorBlockInfo*>(GrowableListIteratorNext(&iterator));
1350 if (successor_block_info == NULL) break;
1351 BasicBlock *succ_bb = successor_block_info->block;
1352 if (succ_bb == bb) {
1353 found = true;
1354 break;
1355 }
1356 }
1357 }
1358 if (found == false) {
1359 char block_name1[BLOCK_NAME_LEN], block_name2[BLOCK_NAME_LEN];
1360 GetBlockName(bb, block_name1);
1361 GetBlockName(pred_bb, block_name2);
1362 DumpCFG("/sdcard/cfg/", false);
1363 LOG(FATAL) << "Successor " << block_name1 << "not found from "
1364 << block_name2;
1365 }
1366 }
1367 return true;
1368}
1369
1370void MIRGraph::VerifyDataflow()
1371{
1372 /* Verify if all blocks are connected as claimed */
1373 DataflowIterator iter(this, kAllNodes, false /* not iterative */);
1374 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
1375 VerifyPredInfo(bb);
1376 }
1377}
1378
1379} // namespace art