1 /*
2 * Copyright (C) 2009 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 "Dalvik.h"
18 #include "Dataflow.h"
19 #include "Loop.h"
20 #include "libdex/DexOpcodes.h"
21
22 /*
23 * Main table containing data flow attributes for each bytecode. The
24 * first kNumPackedOpcodes entries are for Dalvik bytecode
25 * instructions, where extended opcode at the MIR level are appended
26 * afterwards.
27 *
28 * TODO - many optimization flags are incomplete - they will only limit the
29 * scope of optimizations but will not cause mis-optimizations.
30 */
31 int dvmCompilerDataFlowAttributes[kMirOpLast] = {
32 // 00 OP_NOP
33 DF_NOP,
34
35 // 01 OP_MOVE vA, vB
36 DF_DA | DF_UB | DF_IS_MOVE,
37
38 // 02 OP_MOVE_FROM16 vAA, vBBBB
39 DF_DA | DF_UB | DF_IS_MOVE,
40
41 // 03 OP_MOVE_16 vAAAA, vBBBB
42 DF_DA | DF_UB | DF_IS_MOVE,
43
44 // 04 OP_MOVE_WIDE vA, vB
45 DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
46
47 // 05 OP_MOVE_WIDE_FROM16 vAA, vBBBB
48 DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
49
50 // 06 OP_MOVE_WIDE_16 vAAAA, vBBBB
51 DF_DA_WIDE | DF_UB_WIDE | DF_IS_MOVE,
52
53 // 07 OP_MOVE_OBJECT vA, vB
54 DF_DA | DF_UB | DF_IS_MOVE,
55
56 // 08 OP_MOVE_OBJECT_FROM16 vAA, vBBBB
57 DF_DA | DF_UB | DF_IS_MOVE,
58
59 // 09 OP_MOVE_OBJECT_16 vAAAA, vBBBB
60 DF_DA | DF_UB | DF_IS_MOVE,
61
62 // 0A OP_MOVE_RESULT vAA
63 DF_DA,
64
65 // 0B OP_MOVE_RESULT_WIDE vAA
66 DF_DA_WIDE,
67
68 // 0C OP_MOVE_RESULT_OBJECT vAA
69 DF_DA,
70
71 // 0D OP_MOVE_EXCEPTION vAA
72 DF_DA,
73
74 // 0E OP_RETURN_VOID
75 DF_NOP,
76
77 // 0F OP_RETURN vAA
78 DF_UA,
79
80 // 10 OP_RETURN_WIDE vAA
81 DF_UA_WIDE,
82
83 // 11 OP_RETURN_OBJECT vAA
84 DF_UA,
85
86 // 12 OP_CONST_4 vA, #+B
87 DF_DA | DF_SETS_CONST,
88
89 // 13 OP_CONST_16 vAA, #+BBBB
90 DF_DA | DF_SETS_CONST,
91
92 // 14 OP_CONST vAA, #+BBBBBBBB
93 DF_DA | DF_SETS_CONST,
94
95 // 15 OP_CONST_HIGH16 VAA, #+BBBB0000
96 DF_DA | DF_SETS_CONST,
97
98 // 16 OP_CONST_WIDE_16 vAA, #+BBBB
99 DF_DA_WIDE | DF_SETS_CONST,
100
101 // 17 OP_CONST_WIDE_32 vAA, #+BBBBBBBB
102 DF_DA_WIDE | DF_SETS_CONST,
103
104 // 18 OP_CONST_WIDE vAA, #+BBBBBBBBBBBBBBBB
105 DF_DA_WIDE | DF_SETS_CONST,
106
107 // 19 OP_CONST_WIDE_HIGH16 vAA, #+BBBB000000000000
108 DF_DA_WIDE | DF_SETS_CONST,
109
110 // 1A OP_CONST_STRING vAA, string@BBBB
111 DF_DA,
112
113 // 1B OP_CONST_STRING_JUMBO vAA, string@BBBBBBBB
114 DF_DA,
115
116 // 1C OP_CONST_CLASS vAA, type@BBBB
117 DF_DA,
118
119 // 1D OP_MONITOR_ENTER vAA
120 DF_UA,
121
122 // 1E OP_MONITOR_EXIT vAA
123 DF_UA,
124
125 // 1F OP_CHECK_CAST vAA, type@BBBB
126 DF_UA,
127
128 // 20 OP_INSTANCE_OF vA, vB, type@CCCC
129 DF_DA | DF_UB,
130
131 // 21 OP_ARRAY_LENGTH vA, vB
132 DF_DA | DF_UB,
133
134 // 22 OP_NEW_INSTANCE vAA, type@BBBB
135 DF_DA,
136
137 // 23 OP_NEW_ARRAY vA, vB, type@CCCC
138 DF_DA | DF_UB,
139
140 // 24 OP_FILLED_NEW_ARRAY {vD, vE, vF, vG, vA}
141 DF_FORMAT_35C,
142
143 // 25 OP_FILLED_NEW_ARRAY_RANGE {vCCCC .. vNNNN}, type@BBBB
144 DF_FORMAT_3RC,
145
146 // 26 OP_FILL_ARRAY_DATA vAA, +BBBBBBBB
147 DF_UA,
148
149 // 27 OP_THROW vAA
150 DF_UA,
151
152 // 28 OP_GOTO
153 DF_NOP,
154
155 // 29 OP_GOTO_16
156 DF_NOP,
157
158 // 2A OP_GOTO_32
159 DF_NOP,
160
161 // 2B OP_PACKED_SWITCH vAA, +BBBBBBBB
162 DF_UA,
163
164 // 2C OP_SPARSE_SWITCH vAA, +BBBBBBBB
165 DF_UA,
166
167 // 2D OP_CMPL_FLOAT vAA, vBB, vCC
168 DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C,
169
170 // 2E OP_CMPG_FLOAT vAA, vBB, vCC
171 DF_DA | DF_UB | DF_UC | DF_FP_B | DF_FP_C,
172
173 // 2F OP_CMPL_DOUBLE vAA, vBB, vCC
174 DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_FP_B | DF_FP_C,
175
176 // 30 OP_CMPG_DOUBLE vAA, vBB, vCC
177 DF_DA | DF_UB_WIDE | DF_UC_WIDE | DF_FP_B | DF_FP_C,
178
179 // 31 OP_CMP_LONG vAA, vBB, vCC
180 DF_DA | DF_UB_WIDE | DF_UC_WIDE,
181
182 // 32 OP_IF_EQ vA, vB, +CCCC
183 DF_UA | DF_UB,
184
185 // 33 OP_IF_NE vA, vB, +CCCC
186 DF_UA | DF_UB,
187
188 // 34 OP_IF_LT vA, vB, +CCCC
189 DF_UA | DF_UB,
190
191 // 35 OP_IF_GE vA, vB, +CCCC
192 DF_UA | DF_UB,
193
194 // 36 OP_IF_GT vA, vB, +CCCC
195 DF_UA | DF_UB,
196
197 // 37 OP_IF_LE vA, vB, +CCCC
198 DF_UA | DF_UB,
199
200
201 // 38 OP_IF_EQZ vAA, +BBBB
202 DF_UA,
203
204 // 39 OP_IF_NEZ vAA, +BBBB
205 DF_UA,
206
207 // 3A OP_IF_LTZ vAA, +BBBB
208 DF_UA,
209
210 // 3B OP_IF_GEZ vAA, +BBBB
211 DF_UA,
212
213 // 3C OP_IF_GTZ vAA, +BBBB
214 DF_UA,
215
216 // 3D OP_IF_LEZ vAA, +BBBB
217 DF_UA,
218
219 // 3E OP_UNUSED_3E
220 DF_NOP,
221
222 // 3F OP_UNUSED_3F
223 DF_NOP,
224
225 // 40 OP_UNUSED_40
226 DF_NOP,
227
228 // 41 OP_UNUSED_41
229 DF_NOP,
230
231 // 42 OP_UNUSED_42
232 DF_NOP,
233
234 // 43 OP_UNUSED_43
235 DF_NOP,
236
237 // 44 OP_AGET vAA, vBB, vCC
238 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
239
240 // 45 OP_AGET_WIDE vAA, vBB, vCC
241 DF_DA_WIDE | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
242
243 // 46 OP_AGET_OBJECT vAA, vBB, vCC
244 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
245
246 // 47 OP_AGET_BOOLEAN vAA, vBB, vCC
247 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
248
249 // 48 OP_AGET_BYTE vAA, vBB, vCC
250 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
251
252 // 49 OP_AGET_CHAR vAA, vBB, vCC
253 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
254
255 // 4A OP_AGET_SHORT vAA, vBB, vCC
256 DF_DA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_0 | DF_IS_GETTER,
257
258 // 4B OP_APUT vAA, vBB, vCC
259 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
260
261 // 4C OP_APUT_WIDE vAA, vBB, vCC
262 DF_UA_WIDE | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_2 | DF_IS_SETTER,
263
264 // 4D OP_APUT_OBJECT vAA, vBB, vCC
265 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
266
267 // 4E OP_APUT_BOOLEAN vAA, vBB, vCC
268 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
269
270 // 4F OP_APUT_BYTE vAA, vBB, vCC
271 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
272
273 // 50 OP_APUT_CHAR vAA, vBB, vCC
274 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
275
276 // 51 OP_APUT_SHORT vAA, vBB, vCC
277 DF_UA | DF_UB | DF_UC | DF_NULL_N_RANGE_CHECK_1 | DF_IS_SETTER,
278
279 // 52 OP_IGET vA, vB, field@CCCC
280 DF_DA | DF_UB | DF_IS_GETTER,
281
282 // 53 OP_IGET_WIDE vA, vB, field@CCCC
283 DF_DA_WIDE | DF_UB | DF_IS_GETTER,
284
285 // 54 OP_IGET_OBJECT vA, vB, field@CCCC
286 DF_DA | DF_UB | DF_IS_GETTER,
287
288 // 55 OP_IGET_BOOLEAN vA, vB, field@CCCC
289 DF_DA | DF_UB | DF_IS_GETTER,
290
291 // 56 OP_IGET_BYTE vA, vB, field@CCCC
292 DF_DA | DF_UB | DF_IS_GETTER,
293
294 // 57 OP_IGET_CHAR vA, vB, field@CCCC
295 DF_DA | DF_UB | DF_IS_GETTER,
296
297 // 58 OP_IGET_SHORT vA, vB, field@CCCC
298 DF_DA | DF_UB | DF_IS_GETTER,
299
300 // 59 OP_IPUT vA, vB, field@CCCC
301 DF_UA | DF_UB | DF_IS_SETTER,
302
303 // 5A OP_IPUT_WIDE vA, vB, field@CCCC
304 DF_UA_WIDE | DF_UB | DF_IS_SETTER,
305
306 // 5B OP_IPUT_OBJECT vA, vB, field@CCCC
307 DF_UA | DF_UB | DF_IS_SETTER,
308
309 // 5C OP_IPUT_BOOLEAN vA, vB, field@CCCC
310 DF_UA | DF_UB | DF_IS_SETTER,
311
312 // 5D OP_IPUT_BYTE vA, vB, field@CCCC
313 DF_UA | DF_UB | DF_IS_SETTER,
314
315 // 5E OP_IPUT_CHAR vA, vB, field@CCCC
316 DF_UA | DF_UB | DF_IS_SETTER,
317
318 // 5F OP_IPUT_SHORT vA, vB, field@CCCC
319 DF_UA | DF_UB | DF_IS_SETTER,
320
321 // 60 OP_SGET vAA, field@BBBB
322 DF_DA | DF_IS_GETTER,
323
324 // 61 OP_SGET_WIDE vAA, field@BBBB
325 DF_DA_WIDE | DF_IS_GETTER,
326
327 // 62 OP_SGET_OBJECT vAA, field@BBBB
328 DF_DA | DF_IS_GETTER,
329
330 // 63 OP_SGET_BOOLEAN vAA, field@BBBB
331 DF_DA | DF_IS_GETTER,
332
333 // 64 OP_SGET_BYTE vAA, field@BBBB
334 DF_DA | DF_IS_GETTER,
335
336 // 65 OP_SGET_CHAR vAA, field@BBBB
337 DF_DA | DF_IS_GETTER,
338
339 // 66 OP_SGET_SHORT vAA, field@BBBB
340 DF_DA | DF_IS_GETTER,
341
342 // 67 OP_SPUT vAA, field@BBBB
343 DF_UA | DF_IS_SETTER,
344
345 // 68 OP_SPUT_WIDE vAA, field@BBBB
346 DF_UA_WIDE | DF_IS_SETTER,
347
348 // 69 OP_SPUT_OBJECT vAA, field@BBBB
349 DF_UA | DF_IS_SETTER,
350
351 // 6A OP_SPUT_BOOLEAN vAA, field@BBBB
352 DF_UA | DF_IS_SETTER,
353
354 // 6B OP_SPUT_BYTE vAA, field@BBBB
355 DF_UA | DF_IS_SETTER,
356
357 // 6C OP_SPUT_CHAR vAA, field@BBBB
358 DF_UA | DF_IS_SETTER,
359
360 // 6D OP_SPUT_SHORT vAA, field@BBBB
361 DF_UA | DF_IS_SETTER,
362
363 // 6E OP_INVOKE_VIRTUAL {vD, vE, vF, vG, vA}
364 DF_FORMAT_35C,
365
366 // 6F OP_INVOKE_SUPER {vD, vE, vF, vG, vA}
367 DF_FORMAT_35C,
368
369 // 70 OP_INVOKE_DIRECT {vD, vE, vF, vG, vA}
370 DF_FORMAT_35C,
371
372 // 71 OP_INVOKE_STATIC {vD, vE, vF, vG, vA}
373 DF_FORMAT_35C,
374
375 // 72 OP_INVOKE_INTERFACE {vD, vE, vF, vG, vA}
376 DF_FORMAT_35C,
377
378 // 73 OP_UNUSED_73
379 DF_NOP,
380
381 // 74 OP_INVOKE_VIRTUAL_RANGE {vCCCC .. vNNNN}
382 DF_FORMAT_3RC,
383
384 // 75 OP_INVOKE_SUPER_RANGE {vCCCC .. vNNNN}
385 DF_FORMAT_3RC,
386
387 // 76 OP_INVOKE_DIRECT_RANGE {vCCCC .. vNNNN}
388 DF_FORMAT_3RC,
389
390 // 77 OP_INVOKE_STATIC_RANGE {vCCCC .. vNNNN}
391 DF_FORMAT_3RC,
392
393 // 78 OP_INVOKE_INTERFACE_RANGE {vCCCC .. vNNNN}
394 DF_FORMAT_3RC,
395
396 // 79 OP_UNUSED_79
397 DF_NOP,
398
399 // 7A OP_UNUSED_7A
400 DF_NOP,
401
402 // 7B OP_NEG_INT vA, vB
403 DF_DA | DF_UB,
404
405 // 7C OP_NOT_INT vA, vB
406 DF_DA | DF_UB,
407
408 // 7D OP_NEG_LONG vA, vB
409 DF_DA_WIDE | DF_UB_WIDE,
410
411 // 7E OP_NOT_LONG vA, vB
412 DF_DA_WIDE | DF_UB_WIDE,
413
414 // 7F OP_NEG_FLOAT vA, vB
415 DF_DA | DF_UB | DF_FP_A | DF_FP_B,
416
417 // 80 OP_NEG_DOUBLE vA, vB
418 DF_DA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
419
420 // 81 OP_INT_TO_LONG vA, vB
421 DF_DA_WIDE | DF_UB,
422
423 // 82 OP_INT_TO_FLOAT vA, vB
424 DF_DA | DF_UB | DF_FP_A,
425
426 // 83 OP_INT_TO_DOUBLE vA, vB
427 DF_DA_WIDE | DF_UB | DF_FP_A,
428
429 // 84 OP_LONG_TO_INT vA, vB
430 DF_DA | DF_UB_WIDE,
431
432 // 85 OP_LONG_TO_FLOAT vA, vB
433 DF_DA | DF_UB_WIDE | DF_FP_A,
434
435 // 86 OP_LONG_TO_DOUBLE vA, vB
436 DF_DA_WIDE | DF_UB_WIDE | DF_FP_A,
437
438 // 87 OP_FLOAT_TO_INT vA, vB
439 DF_DA | DF_UB | DF_FP_B,
440
441 // 88 OP_FLOAT_TO_LONG vA, vB
442 DF_DA_WIDE | DF_UB | DF_FP_B,
443
444 // 89 OP_FLOAT_TO_DOUBLE vA, vB
445 DF_DA_WIDE | DF_UB | DF_FP_A | DF_FP_B,
446
447 // 8A OP_DOUBLE_TO_INT vA, vB
448 DF_DA | DF_UB_WIDE | DF_FP_B,
449
450 // 8B OP_DOUBLE_TO_LONG vA, vB
451 DF_DA_WIDE | DF_UB_WIDE | DF_FP_B,
452
453 // 8C OP_DOUBLE_TO_FLOAT vA, vB
454 DF_DA | DF_UB_WIDE | DF_FP_A | DF_FP_B,
455
456 // 8D OP_INT_TO_BYTE vA, vB
457 DF_DA | DF_UB,
458
459 // 8E OP_INT_TO_CHAR vA, vB
460 DF_DA | DF_UB,
461
462 // 8F OP_INT_TO_SHORT vA, vB
463 DF_DA | DF_UB,
464
465 // 90 OP_ADD_INT vAA, vBB, vCC
466 DF_DA | DF_UB | DF_UC | DF_IS_LINEAR,
467
468 // 91 OP_SUB_INT vAA, vBB, vCC
469 DF_DA | DF_UB | DF_UC | DF_IS_LINEAR,
470
471 // 92 OP_MUL_INT vAA, vBB, vCC
472 DF_DA | DF_UB | DF_UC,
473
474 // 93 OP_DIV_INT vAA, vBB, vCC
475 DF_DA | DF_UB | DF_UC,
476
477 // 94 OP_REM_INT vAA, vBB, vCC
478 DF_DA | DF_UB | DF_UC,
479
480 // 95 OP_AND_INT vAA, vBB, vCC
481 DF_DA | DF_UB | DF_UC,
482
483 // 96 OP_OR_INT vAA, vBB, vCC
484 DF_DA | DF_UB | DF_UC,
485
486 // 97 OP_XOR_INT vAA, vBB, vCC
487 DF_DA | DF_UB | DF_UC,
488
489 // 98 OP_SHL_INT vAA, vBB, vCC
490 DF_DA | DF_UB | DF_UC,
491
492 // 99 OP_SHR_INT vAA, vBB, vCC
493 DF_DA | DF_UB | DF_UC,
494
495 // 9A OP_USHR_INT vAA, vBB, vCC
496 DF_DA | DF_UB | DF_UC,
497
498 // 9B OP_ADD_LONG vAA, vBB, vCC
499 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
500
501 // 9C OP_SUB_LONG vAA, vBB, vCC
502 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
503
504 // 9D OP_MUL_LONG vAA, vBB, vCC
505 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
506
507 // 9E OP_DIV_LONG vAA, vBB, vCC
508 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
509
510 // 9F OP_REM_LONG vAA, vBB, vCC
511 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
512
513 // A0 OP_AND_LONG vAA, vBB, vCC
514 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
515
516 // A1 OP_OR_LONG vAA, vBB, vCC
517 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
518
519 // A2 OP_XOR_LONG vAA, vBB, vCC
520 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE,
521
522 // A3 OP_SHL_LONG vAA, vBB, vCC
523 DF_DA_WIDE | DF_UB_WIDE | DF_UC,
524
525 // A4 OP_SHR_LONG vAA, vBB, vCC
526 DF_DA_WIDE | DF_UB_WIDE | DF_UC,
527
528 // A5 OP_USHR_LONG vAA, vBB, vCC
529 DF_DA_WIDE | DF_UB_WIDE | DF_UC,
530
531 // A6 OP_ADD_FLOAT vAA, vBB, vCC
532 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
533
534 // A7 OP_SUB_FLOAT vAA, vBB, vCC
535 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
536
537 // A8 OP_MUL_FLOAT vAA, vBB, vCC
538 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
539
540 // A9 OP_DIV_FLOAT vAA, vBB, vCC
541 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
542
543 // AA OP_REM_FLOAT vAA, vBB, vCC
544 DF_DA | DF_UB | DF_UC | DF_FP_A | DF_FP_B | DF_FP_C,
545
546 // AB OP_ADD_DOUBLE vAA, vBB, vCC
547 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
548
549 // AC OP_SUB_DOUBLE vAA, vBB, vCC
550 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
551
552 // AD OP_MUL_DOUBLE vAA, vBB, vCC
553 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
554
555 // AE OP_DIV_DOUBLE vAA, vBB, vCC
556 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
557
558 // AF OP_REM_DOUBLE vAA, vBB, vCC
559 DF_DA_WIDE | DF_UB_WIDE | DF_UC_WIDE | DF_FP_A | DF_FP_B | DF_FP_C,
560
561 // B0 OP_ADD_INT_2ADDR vA, vB
562 DF_DA | DF_UA | DF_UB,
563
564 // B1 OP_SUB_INT_2ADDR vA, vB
565 DF_DA | DF_UA | DF_UB,
566
567 // B2 OP_MUL_INT_2ADDR vA, vB
568 DF_DA | DF_UA | DF_UB,
569
570 // B3 OP_DIV_INT_2ADDR vA, vB
571 DF_DA | DF_UA | DF_UB,
572
573 // B4 OP_REM_INT_2ADDR vA, vB
574 DF_DA | DF_UA | DF_UB,
575
576 // B5 OP_AND_INT_2ADDR vA, vB
577 DF_DA | DF_UA | DF_UB,
578
579 // B6 OP_OR_INT_2ADDR vA, vB
580 DF_DA | DF_UA | DF_UB,
581
582 // B7 OP_XOR_INT_2ADDR vA, vB
583 DF_DA | DF_UA | DF_UB,
584
585 // B8 OP_SHL_INT_2ADDR vA, vB
586 DF_DA | DF_UA | DF_UB,
587
588 // B9 OP_SHR_INT_2ADDR vA, vB
589 DF_DA | DF_UA | DF_UB,
590
591 // BA OP_USHR_INT_2ADDR vA, vB
592 DF_DA | DF_UA | DF_UB,
593
594 // BB OP_ADD_LONG_2ADDR vA, vB
595 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
596
597 // BC OP_SUB_LONG_2ADDR vA, vB
598 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
599
600 // BD OP_MUL_LONG_2ADDR vA, vB
601 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
602
603 // BE OP_DIV_LONG_2ADDR vA, vB
604 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
605
606 // BF OP_REM_LONG_2ADDR vA, vB
607 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
608
609 // C0 OP_AND_LONG_2ADDR vA, vB
610 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
611
612 // C1 OP_OR_LONG_2ADDR vA, vB
613 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
614
615 // C2 OP_XOR_LONG_2ADDR vA, vB
616 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE,
617
618 // C3 OP_SHL_LONG_2ADDR vA, vB
619 DF_DA_WIDE | DF_UA_WIDE | DF_UB,
620
621 // C4 OP_SHR_LONG_2ADDR vA, vB
622 DF_DA_WIDE | DF_UA_WIDE | DF_UB,
623
624 // C5 OP_USHR_LONG_2ADDR vA, vB
625 DF_DA_WIDE | DF_UA_WIDE | DF_UB,
626
627 // C6 OP_ADD_FLOAT_2ADDR vA, vB
628 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
629
630 // C7 OP_SUB_FLOAT_2ADDR vA, vB
631 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
632
633 // C8 OP_MUL_FLOAT_2ADDR vA, vB
634 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
635
636 // C9 OP_DIV_FLOAT_2ADDR vA, vB
637 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
638
639 // CA OP_REM_FLOAT_2ADDR vA, vB
640 DF_DA | DF_UA | DF_UB | DF_FP_A | DF_FP_B,
641
642 // CB OP_ADD_DOUBLE_2ADDR vA, vB
643 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
644
645 // CC OP_SUB_DOUBLE_2ADDR vA, vB
646 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
647
648 // CD OP_MUL_DOUBLE_2ADDR vA, vB
649 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
650
651 // CE OP_DIV_DOUBLE_2ADDR vA, vB
652 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
653
654 // CF OP_REM_DOUBLE_2ADDR vA, vB
655 DF_DA_WIDE | DF_UA_WIDE | DF_UB_WIDE | DF_FP_A | DF_FP_B,
656
657 // D0 OP_ADD_INT_LIT16 vA, vB, #+CCCC
658 DF_DA | DF_UB,
659
660 // D1 OP_RSUB_INT vA, vB, #+CCCC
661 DF_DA | DF_UB,
662
663 // D2 OP_MUL_INT_LIT16 vA, vB, #+CCCC
664 DF_DA | DF_UB,
665
666 // D3 OP_DIV_INT_LIT16 vA, vB, #+CCCC
667 DF_DA | DF_UB,
668
669 // D4 OP_REM_INT_LIT16 vA, vB, #+CCCC
670 DF_DA | DF_UB,
671
672 // D5 OP_AND_INT_LIT16 vA, vB, #+CCCC
673 DF_DA | DF_UB,
674
675 // D6 OP_OR_INT_LIT16 vA, vB, #+CCCC
676 DF_DA | DF_UB,
677
678 // D7 OP_XOR_INT_LIT16 vA, vB, #+CCCC
679 DF_DA | DF_UB,
680
681 // D8 OP_ADD_INT_LIT8 vAA, vBB, #+CC
682 DF_DA | DF_UB | DF_IS_LINEAR,
683
684 // D9 OP_RSUB_INT_LIT8 vAA, vBB, #+CC
685 DF_DA | DF_UB,
686
687 // DA OP_MUL_INT_LIT8 vAA, vBB, #+CC
688 DF_DA | DF_UB,
689
690 // DB OP_DIV_INT_LIT8 vAA, vBB, #+CC
691 DF_DA | DF_UB,
692
693 // DC OP_REM_INT_LIT8 vAA, vBB, #+CC
694 DF_DA | DF_UB,
695
696 // DD OP_AND_INT_LIT8 vAA, vBB, #+CC
697 DF_DA | DF_UB,
698
699 // DE OP_OR_INT_LIT8 vAA, vBB, #+CC
700 DF_DA | DF_UB,
701
702 // DF OP_XOR_INT_LIT8 vAA, vBB, #+CC
703 DF_DA | DF_UB,
704
705 // E0 OP_SHL_INT_LIT8 vAA, vBB, #+CC
706 DF_DA | DF_UB,
707
708 // E1 OP_SHR_INT_LIT8 vAA, vBB, #+CC
709 DF_DA | DF_UB,
710
711 // E2 OP_USHR_INT_LIT8 vAA, vBB, #+CC
712 DF_DA | DF_UB,
713
714 // E3 OP_IGET_VOLATILE
715 DF_DA | DF_UB,
716
717 // E4 OP_IPUT_VOLATILE
718 DF_UA | DF_UB,
719
720 // E5 OP_SGET_VOLATILE
721 DF_DA,
722
723 // E6 OP_SPUT_VOLATILE
724 DF_UA,
725
726 // E7 OP_IGET_OBJECT_VOLATILE
727 DF_DA | DF_UB,
728
729 // E8 OP_IGET_WIDE_VOLATILE
730 DF_DA_WIDE | DF_UB,
731
732 // E9 OP_IPUT_WIDE_VOLATILE
733 DF_UA_WIDE | DF_UB,
734
735 // EA OP_SGET_WIDE_VOLATILE
736 DF_DA_WIDE,
737
738 // EB OP_SPUT_WIDE_VOLATILE
739 DF_UA_WIDE,
740
741 // EC OP_BREAKPOINT
742 DF_NOP,
743
744 // ED OP_THROW_VERIFICATION_ERROR
745 DF_NOP,
746
747 // EE OP_EXECUTE_INLINE
748 DF_FORMAT_35C,
749
750 // EF OP_EXECUTE_INLINE_RANGE
751 DF_FORMAT_3RC,
752
753 // F0 OP_INVOKE_OBJECT_INIT_RANGE
754 DF_NOP,
755
756 // F1 OP_RETURN_VOID_BARRIER
757 DF_NOP,
758
759 // F2 OP_IGET_QUICK
760 DF_DA | DF_UB | DF_IS_GETTER,
761
762 // F3 OP_IGET_WIDE_QUICK
763 DF_DA_WIDE | DF_UB | DF_IS_GETTER,
764
765 // F4 OP_IGET_OBJECT_QUICK
766 DF_DA | DF_UB | DF_IS_GETTER,
767
768 // F5 OP_IPUT_QUICK
769 DF_UA | DF_UB | DF_IS_SETTER,
770
771 // F6 OP_IPUT_WIDE_QUICK
772 DF_UA_WIDE | DF_UB | DF_IS_SETTER,
773
774 // F7 OP_IPUT_OBJECT_QUICK
775 DF_UA | DF_UB | DF_IS_SETTER,
776
777 // F8 OP_INVOKE_VIRTUAL_QUICK
778 DF_FORMAT_35C,
779
780 // F9 OP_INVOKE_VIRTUAL_QUICK_RANGE
781 DF_FORMAT_3RC,
782
783 // FA OP_INVOKE_SUPER_QUICK
784 DF_FORMAT_35C,
785
786 // FB OP_INVOKE_SUPER_QUICK_RANGE
787 DF_FORMAT_3RC,
788
789 // FC OP_IPUT_OBJECT_VOLATILE
790 DF_UA | DF_UB,
791
792 // FD OP_SGET_OBJECT_VOLATILE
793 DF_DA,
794
795 // FE OP_SPUT_OBJECT_VOLATILE
796 DF_UA,
797
798 // FF OP_UNUSED_FF
799 DF_NOP,
800
801 // Beginning of extended MIR opcodes
802 // 100 OP_MIR_PHI
803 DF_PHI | DF_DA,
804 /*
805 * For extended MIR inserted at the MIR2LIR stage, it is okay to have
806 * undefined values here.
807 */
808 };
809
810 /* Return the Dalvik register/subscript pair of a given SSA register */
dvmConvertSSARegToDalvik(const CompilationUnit * cUnit,int ssaReg)811 int dvmConvertSSARegToDalvik(const CompilationUnit *cUnit, int ssaReg)
812 {
813 return GET_ELEM_N(cUnit->ssaToDalvikMap, int, ssaReg);
814 }
815
816 /*
817 * Utility function to convert encoded SSA register value into Dalvik register
818 * and subscript pair. Each SSA register can be used to index the
819 * ssaToDalvikMap list to get the subscript[31..16]/dalvik_reg[15..0] mapping.
820 */
dvmCompilerGetDalvikDisassembly(const DecodedInstruction * insn,const char * note)821 char *dvmCompilerGetDalvikDisassembly(const DecodedInstruction *insn,
822 const char *note)
823 {
824 char buffer[256];
825 Opcode opcode = insn->opcode;
826 int dfAttributes = dvmCompilerDataFlowAttributes[opcode];
827 int flags;
828 char *ret;
829
830 buffer[0] = 0;
831 if ((int)opcode >= (int)kMirOpFirst) {
832 if ((int)opcode == (int)kMirOpPhi) {
833 strcpy(buffer, "PHI");
834 }
835 else {
836 sprintf(buffer, "Opcode %#x", opcode);
837 }
838 flags = 0;
839 } else {
840 strcpy(buffer, dexGetOpcodeName(opcode));
841 flags = dexGetFlagsFromOpcode(insn->opcode);
842 }
843
844 if (note)
845 strcat(buffer, note);
846
847 /* For branches, decode the instructions to print out the branch targets */
848 if (flags & kInstrCanBranch) {
849 InstructionFormat dalvikFormat = dexGetFormatFromOpcode(insn->opcode);
850 int offset = 0;
851 switch (dalvikFormat) {
852 case kFmt21t:
853 snprintf(buffer + strlen(buffer), 256, " v%d,", insn->vA);
854 offset = (int) insn->vB;
855 break;
856 case kFmt22t:
857 snprintf(buffer + strlen(buffer), 256, " v%d, v%d,",
858 insn->vA, insn->vB);
859 offset = (int) insn->vC;
860 break;
861 case kFmt10t:
862 case kFmt20t:
863 case kFmt30t:
864 offset = (int) insn->vA;
865 break;
866 default:
867 ALOGE("Unexpected branch format %d / opcode %#x", dalvikFormat,
868 opcode);
869 dvmAbort();
870 break;
871 }
872 snprintf(buffer + strlen(buffer), 256, " (%c%x)",
873 offset > 0 ? '+' : '-',
874 offset > 0 ? offset : -offset);
875 } else if (dfAttributes & DF_FORMAT_35C) {
876 unsigned int i;
877 for (i = 0; i < insn->vA; i++) {
878 if (i != 0) strcat(buffer, ",");
879 snprintf(buffer + strlen(buffer), 256, " v%d", insn->arg[i]);
880 }
881 }
882 else if (dfAttributes & DF_FORMAT_3RC) {
883 snprintf(buffer + strlen(buffer), 256,
884 " v%d..v%d", insn->vC, insn->vC + insn->vA - 1);
885 }
886 else {
887 if (dfAttributes & DF_A_IS_REG) {
888 snprintf(buffer + strlen(buffer), 256, " v%d", insn->vA);
889 }
890 if (dfAttributes & DF_B_IS_REG) {
891 snprintf(buffer + strlen(buffer), 256, ", v%d", insn->vB);
892 }
893 else if ((int)opcode < (int)kMirOpFirst) {
894 snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn->vB);
895 }
896 if (dfAttributes & DF_C_IS_REG) {
897 snprintf(buffer + strlen(buffer), 256, ", v%d", insn->vC);
898 }
899 else if ((int)opcode < (int)kMirOpFirst) {
900 snprintf(buffer + strlen(buffer), 256, ", (#%d)", insn->vC);
901 }
902 }
903 int length = strlen(buffer) + 1;
904 ret = (char *)dvmCompilerNew(length, false);
905 memcpy(ret, buffer, length);
906 return ret;
907 }
908
getSSAName(const CompilationUnit * cUnit,int ssaReg,char * name)909 char *getSSAName(const CompilationUnit *cUnit, int ssaReg, char *name)
910 {
911 int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaReg);
912
913 sprintf(name, "v%d_%d",
914 DECODE_REG(ssa2DalvikValue), DECODE_SUB(ssa2DalvikValue));
915 return name;
916 }
917
918 /*
919 * Dalvik instruction disassembler with optional SSA printing.
920 */
dvmCompilerFullDisassembler(const CompilationUnit * cUnit,const MIR * mir)921 char *dvmCompilerFullDisassembler(const CompilationUnit *cUnit,
922 const MIR *mir)
923 {
924 char buffer[256];
925 char operand0[256], operand1[256];
926 const DecodedInstruction *insn = &mir->dalvikInsn;
927 int opcode = insn->opcode;
928 int dfAttributes = dvmCompilerDataFlowAttributes[opcode];
929 char *ret;
930 int length;
931 OpcodeFlags flags;
932
933 buffer[0] = 0;
934 if (opcode >= kMirOpFirst) {
935 if (opcode == kMirOpPhi) {
936 snprintf(buffer, 256, "PHI %s = (%s",
937 getSSAName(cUnit, mir->ssaRep->defs[0], operand0),
938 getSSAName(cUnit, mir->ssaRep->uses[0], operand1));
939 int i;
940 for (i = 1; i < mir->ssaRep->numUses; i++) {
941 snprintf(buffer + strlen(buffer), 256, ", %s",
942 getSSAName(cUnit, mir->ssaRep->uses[i], operand0));
943 }
944 snprintf(buffer + strlen(buffer), 256, ")");
945 }
946 else {
947 sprintf(buffer, "Opcode %#x", opcode);
948 }
949 goto done;
950 } else {
951 strcpy(buffer, dexGetOpcodeName((Opcode)opcode));
952 }
953
954 flags = dexGetFlagsFromOpcode((Opcode)opcode);
955 /* For branches, decode the instructions to print out the branch targets */
956 if (flags & kInstrCanBranch) {
957 InstructionFormat dalvikFormat = dexGetFormatFromOpcode(insn->opcode);
958 int delta = 0;
959 switch (dalvikFormat) {
960 case kFmt21t:
961 snprintf(buffer + strlen(buffer), 256, " %s, ",
962 getSSAName(cUnit, mir->ssaRep->uses[0], operand0));
963 delta = (int) insn->vB;
964 break;
965 case kFmt22t:
966 snprintf(buffer + strlen(buffer), 256, " %s, %s, ",
967 getSSAName(cUnit, mir->ssaRep->uses[0], operand0),
968 getSSAName(cUnit, mir->ssaRep->uses[1], operand1));
969 delta = (int) insn->vC;
970 break;
971 case kFmt10t:
972 case kFmt20t:
973 case kFmt30t:
974 delta = (int) insn->vA;
975 break;
976 default:
977 ALOGE("Unexpected branch format: %d", dalvikFormat);
978 dvmAbort();
979 break;
980 }
981 snprintf(buffer + strlen(buffer), 256, " %04x",
982 mir->offset + delta);
983 } else if (dfAttributes & (DF_FORMAT_35C | DF_FORMAT_3RC)) {
984 unsigned int i;
985 for (i = 0; i < insn->vA; i++) {
986 if (i != 0) strcat(buffer, ",");
987 snprintf(buffer + strlen(buffer), 256, " %s",
988 getSSAName(cUnit, mir->ssaRep->uses[i], operand0));
989 }
990 } else {
991 int udIdx;
992 if (mir->ssaRep->numDefs) {
993
994 for (udIdx = 0; udIdx < mir->ssaRep->numDefs; udIdx++) {
995 snprintf(buffer + strlen(buffer), 256, " %s",
996 getSSAName(cUnit, mir->ssaRep->defs[udIdx], operand0));
997 }
998 strcat(buffer, ",");
999 }
1000 if (mir->ssaRep->numUses) {
1001 /* No leading ',' for the first use */
1002 snprintf(buffer + strlen(buffer), 256, " %s",
1003 getSSAName(cUnit, mir->ssaRep->uses[0], operand0));
1004 for (udIdx = 1; udIdx < mir->ssaRep->numUses; udIdx++) {
1005 snprintf(buffer + strlen(buffer), 256, ", %s",
1006 getSSAName(cUnit, mir->ssaRep->uses[udIdx], operand0));
1007 }
1008 }
1009 if (opcode < kMirOpFirst) {
1010 InstructionFormat dalvikFormat =
1011 dexGetFormatFromOpcode((Opcode)opcode);
1012 switch (dalvikFormat) {
1013 case kFmt11n: // op vA, #+B
1014 case kFmt21s: // op vAA, #+BBBB
1015 case kFmt21h: // op vAA, #+BBBB00000[00000000]
1016 case kFmt31i: // op vAA, #+BBBBBBBB
1017 case kFmt51l: // op vAA, #+BBBBBBBBBBBBBBBB
1018 snprintf(buffer + strlen(buffer), 256, " #%#x", insn->vB);
1019 break;
1020 case kFmt21c: // op vAA, thing@BBBB
1021 case kFmt31c: // op vAA, thing@BBBBBBBB
1022 snprintf(buffer + strlen(buffer), 256, " @%#x", insn->vB);
1023 break;
1024 case kFmt22b: // op vAA, vBB, #+CC
1025 case kFmt22s: // op vA, vB, #+CCCC
1026 snprintf(buffer + strlen(buffer), 256, " #%#x", insn->vC);
1027 break;
1028 case kFmt22c: // op vA, vB, thing@CCCC
1029 case kFmt22cs: // [opt] op vA, vB, field offset CCCC
1030 snprintf(buffer + strlen(buffer), 256, " @%#x", insn->vC);
1031 break;
1032 /* No need for special printing */
1033 default:
1034 break;
1035 }
1036 }
1037 }
1038
1039 done:
1040 length = strlen(buffer) + 1;
1041 ret = (char *) dvmCompilerNew(length, false);
1042 memcpy(ret, buffer, length);
1043 return ret;
1044 }
1045
1046 /*
1047 * Utility function to convert encoded SSA register value into Dalvik register
1048 * and subscript pair. Each SSA register can be used to index the
1049 * ssaToDalvikMap list to get the subscript[31..16]/dalvik_reg[15..0] mapping.
1050 */
dvmCompilerGetSSAString(CompilationUnit * cUnit,SSARepresentation * ssaRep)1051 char *dvmCompilerGetSSAString(CompilationUnit *cUnit, SSARepresentation *ssaRep)
1052 {
1053 char buffer[256];
1054 char *ret;
1055 int i;
1056
1057 buffer[0] = 0;
1058 for (i = 0; i < ssaRep->numDefs; i++) {
1059 int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaRep->defs[i]);
1060
1061 sprintf(buffer + strlen(buffer), "s%d(v%d_%d) ",
1062 ssaRep->defs[i], DECODE_REG(ssa2DalvikValue),
1063 DECODE_SUB(ssa2DalvikValue));
1064 }
1065
1066 if (ssaRep->numDefs) {
1067 strcat(buffer, "<- ");
1068 }
1069
1070 for (i = 0; i < ssaRep->numUses; i++) {
1071 int ssa2DalvikValue = dvmConvertSSARegToDalvik(cUnit, ssaRep->uses[i]);
1072 int len = strlen(buffer);
1073
1074 if (snprintf(buffer + len, 250 - len, "s%d(v%d_%d) ",
1075 ssaRep->uses[i], DECODE_REG(ssa2DalvikValue),
1076 DECODE_SUB(ssa2DalvikValue)) >= (250 - len)) {
1077 strcat(buffer, "...");
1078 break;
1079 }
1080 }
1081
1082 int length = strlen(buffer) + 1;
1083 ret = (char *)dvmCompilerNew(length, false);
1084 memcpy(ret, buffer, length);
1085 return ret;
1086 }
1087
1088 /* Any register that is used before being defined is considered live-in */
handleLiveInUse(BitVector * useV,BitVector * defV,BitVector * liveInV,int dalvikRegId)1089 static inline void handleLiveInUse(BitVector *useV, BitVector *defV,
1090 BitVector *liveInV, int dalvikRegId)
1091 {
1092 dvmCompilerSetBit(useV, dalvikRegId);
1093 if (!dvmIsBitSet(defV, dalvikRegId)) {
1094 dvmCompilerSetBit(liveInV, dalvikRegId);
1095 }
1096 }
1097
1098 /* Mark a reg as being defined */
handleDef(BitVector * defV,int dalvikRegId)1099 static inline void handleDef(BitVector *defV, int dalvikRegId)
1100 {
1101 dvmCompilerSetBit(defV, dalvikRegId);
1102 }
1103
1104 /*
1105 * Find out live-in variables for natural loops. Variables that are live-in in
1106 * the main loop body are considered to be defined in the entry block.
1107 */
dvmCompilerFindLocalLiveIn(CompilationUnit * cUnit,BasicBlock * bb)1108 bool dvmCompilerFindLocalLiveIn(CompilationUnit *cUnit, BasicBlock *bb)
1109 {
1110 MIR *mir;
1111 BitVector *useV, *defV, *liveInV;
1112
1113 if (bb->dataFlowInfo == NULL) return false;
1114
1115 useV = bb->dataFlowInfo->useV =
1116 dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
1117 defV = bb->dataFlowInfo->defV =
1118 dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
1119 liveInV = bb->dataFlowInfo->liveInV =
1120 dvmCompilerAllocBitVector(cUnit->numDalvikRegisters, false);
1121
1122 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1123 int dfAttributes =
1124 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode];
1125 DecodedInstruction *dInsn = &mir->dalvikInsn;
1126
1127 if (dfAttributes & DF_HAS_USES) {
1128 if (dfAttributes & DF_UA) {
1129 handleLiveInUse(useV, defV, liveInV, dInsn->vA);
1130 } else if (dfAttributes & DF_UA_WIDE) {
1131 handleLiveInUse(useV, defV, liveInV, dInsn->vA);
1132 handleLiveInUse(useV, defV, liveInV, dInsn->vA+1);
1133 }
1134 if (dfAttributes & DF_UB) {
1135 handleLiveInUse(useV, defV, liveInV, dInsn->vB);
1136 } else if (dfAttributes & DF_UB_WIDE) {
1137 handleLiveInUse(useV, defV, liveInV, dInsn->vB);
1138 handleLiveInUse(useV, defV, liveInV, dInsn->vB+1);
1139 }
1140 if (dfAttributes & DF_UC) {
1141 handleLiveInUse(useV, defV, liveInV, dInsn->vC);
1142 } else if (dfAttributes & DF_UC_WIDE) {
1143 handleLiveInUse(useV, defV, liveInV, dInsn->vC);
1144 handleLiveInUse(useV, defV, liveInV, dInsn->vC+1);
1145 }
1146 }
1147 if (dfAttributes & DF_HAS_DEFS) {
1148 handleDef(defV, dInsn->vA);
1149 if (dfAttributes & DF_DA_WIDE) {
1150 handleDef(defV, dInsn->vA+1);
1151 }
1152 }
1153 }
1154 return true;
1155 }
1156
1157 /* Find out the latest SSA register for a given Dalvik register */
handleSSAUse(CompilationUnit * cUnit,int * uses,int dalvikReg,int regIndex)1158 static void handleSSAUse(CompilationUnit *cUnit, int *uses, int dalvikReg,
1159 int regIndex)
1160 {
1161 int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
1162 int ssaReg = DECODE_REG(encodedValue);
1163 uses[regIndex] = ssaReg;
1164 }
1165
1166 /* Setup a new SSA register for a given Dalvik register */
handleSSADef(CompilationUnit * cUnit,int * defs,int dalvikReg,int regIndex)1167 static void handleSSADef(CompilationUnit *cUnit, int *defs, int dalvikReg,
1168 int regIndex)
1169 {
1170 int encodedValue = cUnit->dalvikToSSAMap[dalvikReg];
1171 int ssaReg = cUnit->numSSARegs++;
1172 /* Bump up the subscript */
1173 int dalvikSub = DECODE_SUB(encodedValue) + 1;
1174 int newD2SMapping = ENCODE_REG_SUB(ssaReg, dalvikSub);
1175
1176 cUnit->dalvikToSSAMap[dalvikReg] = newD2SMapping;
1177
1178 int newS2DMapping = ENCODE_REG_SUB(dalvikReg, dalvikSub);
1179 dvmInsertGrowableList(cUnit->ssaToDalvikMap, newS2DMapping);
1180
1181 defs[regIndex] = ssaReg;
1182 }
1183
1184 /* Loop up new SSA names for format_35c instructions */
dataFlowSSAFormat35C(CompilationUnit * cUnit,MIR * mir)1185 static void dataFlowSSAFormat35C(CompilationUnit *cUnit, MIR *mir)
1186 {
1187 DecodedInstruction *dInsn = &mir->dalvikInsn;
1188 int numUses = dInsn->vA;
1189 int i;
1190
1191 mir->ssaRep->numUses = numUses;
1192 mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * numUses, false);
1193
1194 for (i = 0; i < numUses; i++) {
1195 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->arg[i], i);
1196 }
1197 }
1198
1199 /* Loop up new SSA names for format_3rc instructions */
dataFlowSSAFormat3RC(CompilationUnit * cUnit,MIR * mir)1200 static void dataFlowSSAFormat3RC(CompilationUnit *cUnit, MIR *mir)
1201 {
1202 DecodedInstruction *dInsn = &mir->dalvikInsn;
1203 int numUses = dInsn->vA;
1204 int i;
1205
1206 mir->ssaRep->numUses = numUses;
1207 mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * numUses, false);
1208
1209 for (i = 0; i < numUses; i++) {
1210 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+i, i);
1211 }
1212 }
1213
1214 /* Entry function to convert a block into SSA representation */
dvmCompilerDoSSAConversion(CompilationUnit * cUnit,BasicBlock * bb)1215 bool dvmCompilerDoSSAConversion(CompilationUnit *cUnit, BasicBlock *bb)
1216 {
1217 MIR *mir;
1218
1219 if (bb->dataFlowInfo == NULL) return false;
1220
1221 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1222 mir->ssaRep = (struct SSARepresentation *)
1223 dvmCompilerNew(sizeof(SSARepresentation), true);
1224
1225 int dfAttributes =
1226 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode];
1227
1228 int numUses = 0;
1229
1230 if (dfAttributes & DF_FORMAT_35C) {
1231 dataFlowSSAFormat35C(cUnit, mir);
1232 continue;
1233 }
1234
1235 if (dfAttributes & DF_FORMAT_3RC) {
1236 dataFlowSSAFormat3RC(cUnit, mir);
1237 continue;
1238 }
1239
1240 if (dfAttributes & DF_HAS_USES) {
1241 if (dfAttributes & DF_UA) {
1242 numUses++;
1243 } else if (dfAttributes & DF_UA_WIDE) {
1244 numUses += 2;
1245 }
1246 if (dfAttributes & DF_UB) {
1247 numUses++;
1248 } else if (dfAttributes & DF_UB_WIDE) {
1249 numUses += 2;
1250 }
1251 if (dfAttributes & DF_UC) {
1252 numUses++;
1253 } else if (dfAttributes & DF_UC_WIDE) {
1254 numUses += 2;
1255 }
1256 }
1257
1258 if (numUses) {
1259 mir->ssaRep->numUses = numUses;
1260 mir->ssaRep->uses = (int *)dvmCompilerNew(sizeof(int) * numUses,
1261 false);
1262 mir->ssaRep->fpUse = (bool *)dvmCompilerNew(sizeof(bool) * numUses,
1263 false);
1264 }
1265
1266 int numDefs = 0;
1267
1268 if (dfAttributes & DF_HAS_DEFS) {
1269 numDefs++;
1270 if (dfAttributes & DF_DA_WIDE) {
1271 numDefs++;
1272 }
1273 }
1274
1275 if (numDefs) {
1276 mir->ssaRep->numDefs = numDefs;
1277 mir->ssaRep->defs = (int *)dvmCompilerNew(sizeof(int) * numDefs,
1278 false);
1279 mir->ssaRep->fpDef = (bool *)dvmCompilerNew(sizeof(bool) * numDefs,
1280 false);
1281 }
1282
1283 DecodedInstruction *dInsn = &mir->dalvikInsn;
1284
1285 if (dfAttributes & DF_HAS_USES) {
1286 numUses = 0;
1287 if (dfAttributes & DF_UA) {
1288 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A;
1289 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++);
1290 } else if (dfAttributes & DF_UA_WIDE) {
1291 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A;
1292 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA, numUses++);
1293 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_A;
1294 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vA+1, numUses++);
1295 }
1296 if (dfAttributes & DF_UB) {
1297 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B;
1298 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++);
1299 } else if (dfAttributes & DF_UB_WIDE) {
1300 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B;
1301 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB, numUses++);
1302 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_B;
1303 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vB+1, numUses++);
1304 }
1305 if (dfAttributes & DF_UC) {
1306 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C;
1307 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++);
1308 } else if (dfAttributes & DF_UC_WIDE) {
1309 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C;
1310 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC, numUses++);
1311 mir->ssaRep->fpUse[numUses] = dfAttributes & DF_FP_C;
1312 handleSSAUse(cUnit, mir->ssaRep->uses, dInsn->vC+1, numUses++);
1313 }
1314 }
1315 if (dfAttributes & DF_HAS_DEFS) {
1316 mir->ssaRep->fpDef[0] = dfAttributes & DF_FP_A;
1317 handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA, 0);
1318 if (dfAttributes & DF_DA_WIDE) {
1319 mir->ssaRep->fpDef[1] = dfAttributes & DF_FP_A;
1320 handleSSADef(cUnit, mir->ssaRep->defs, dInsn->vA+1, 1);
1321 }
1322 }
1323 }
1324
1325 /*
1326 * Take a snapshot of Dalvik->SSA mapping at the end of each block. The
1327 * input to PHI nodes can be derived from the snapshot of all predecessor
1328 * blocks.
1329 */
1330 bb->dataFlowInfo->dalvikToSSAMap =
1331 (int *)dvmCompilerNew(sizeof(int) * cUnit->method->registersSize,
1332 false);
1333
1334 memcpy(bb->dataFlowInfo->dalvikToSSAMap, cUnit->dalvikToSSAMap,
1335 sizeof(int) * cUnit->method->registersSize);
1336 return true;
1337 }
1338
1339 /* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */
setConstant(CompilationUnit * cUnit,int ssaReg,int value)1340 static void setConstant(CompilationUnit *cUnit, int ssaReg, int value)
1341 {
1342 dvmSetBit(cUnit->isConstantV, ssaReg);
1343 cUnit->constantValues[ssaReg] = value;
1344 }
1345
dvmCompilerDoConstantPropagation(CompilationUnit * cUnit,BasicBlock * bb)1346 bool dvmCompilerDoConstantPropagation(CompilationUnit *cUnit, BasicBlock *bb)
1347 {
1348 MIR *mir;
1349 BitVector *isConstantV = cUnit->isConstantV;
1350
1351 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1352 int dfAttributes =
1353 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode];
1354
1355 DecodedInstruction *dInsn = &mir->dalvikInsn;
1356
1357 if (!(dfAttributes & DF_HAS_DEFS)) continue;
1358
1359 /* Handle instructions that set up constants directly */
1360 if (dfAttributes & DF_SETS_CONST) {
1361 if (dfAttributes & DF_DA) {
1362 switch (dInsn->opcode) {
1363 case OP_CONST_4:
1364 case OP_CONST_16:
1365 case OP_CONST:
1366 setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB);
1367 break;
1368 case OP_CONST_HIGH16:
1369 setConstant(cUnit, mir->ssaRep->defs[0],
1370 dInsn->vB << 16);
1371 break;
1372 default:
1373 break;
1374 }
1375 } else if (dfAttributes & DF_DA_WIDE) {
1376 switch (dInsn->opcode) {
1377 case OP_CONST_WIDE_16:
1378 case OP_CONST_WIDE_32:
1379 setConstant(cUnit, mir->ssaRep->defs[0], dInsn->vB);
1380 setConstant(cUnit, mir->ssaRep->defs[1], 0);
1381 break;
1382 case OP_CONST_WIDE:
1383 setConstant(cUnit, mir->ssaRep->defs[0],
1384 (int) dInsn->vB_wide);
1385 setConstant(cUnit, mir->ssaRep->defs[1],
1386 (int) (dInsn->vB_wide >> 32));
1387 break;
1388 case OP_CONST_WIDE_HIGH16:
1389 setConstant(cUnit, mir->ssaRep->defs[0], 0);
1390 setConstant(cUnit, mir->ssaRep->defs[1],
1391 dInsn->vB << 16);
1392 break;
1393 default:
1394 break;
1395 }
1396 }
1397 /* Handle instructions that set up constants directly */
1398 } else if (dfAttributes & DF_IS_MOVE) {
1399 int i;
1400
1401 for (i = 0; i < mir->ssaRep->numUses; i++) {
1402 if (!dvmIsBitSet(isConstantV, mir->ssaRep->uses[i])) break;
1403 }
1404 /* Move a register holding a constant to another register */
1405 if (i == mir->ssaRep->numUses) {
1406 setConstant(cUnit, mir->ssaRep->defs[0],
1407 cUnit->constantValues[mir->ssaRep->uses[0]]);
1408 if (dfAttributes & DF_DA_WIDE) {
1409 setConstant(cUnit, mir->ssaRep->defs[1],
1410 cUnit->constantValues[mir->ssaRep->uses[1]]);
1411 }
1412 }
1413 }
1414 }
1415 /* TODO: implement code to handle arithmetic operations */
1416 return true;
1417 }
1418
dvmCompilerFindInductionVariables(struct CompilationUnit * cUnit,struct BasicBlock * bb)1419 bool dvmCompilerFindInductionVariables(struct CompilationUnit *cUnit,
1420 struct BasicBlock *bb)
1421 {
1422 BitVector *isIndVarV = cUnit->loopAnalysis->isIndVarV;
1423 BitVector *isConstantV = cUnit->isConstantV;
1424 GrowableList *ivList = cUnit->loopAnalysis->ivList;
1425 MIR *mir;
1426
1427 if (bb->blockType != kDalvikByteCode && bb->blockType != kEntryBlock) {
1428 return false;
1429 }
1430
1431 /* If the bb doesn't have a phi it cannot contain an induction variable */
1432 if (bb->firstMIRInsn == NULL ||
1433 (int)bb->firstMIRInsn->dalvikInsn.opcode != (int)kMirOpPhi) {
1434 return false;
1435 }
1436
1437 /* Find basic induction variable first */
1438 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1439 int dfAttributes =
1440 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode];
1441
1442 if (!(dfAttributes & DF_IS_LINEAR)) continue;
1443
1444 /*
1445 * For a basic induction variable:
1446 * 1) use[0] should belong to the output of a phi node
1447 * 2) def[0] should belong to the input of the same phi node
1448 * 3) the value added/subtracted is a constant
1449 */
1450 MIR *phi;
1451 for (phi = bb->firstMIRInsn; phi; phi = phi->next) {
1452 if ((int)phi->dalvikInsn.opcode != (int)kMirOpPhi) break;
1453
1454 if (phi->ssaRep->defs[0] == mir->ssaRep->uses[0] &&
1455 phi->ssaRep->uses[1] == mir->ssaRep->defs[0]) {
1456 bool deltaIsConstant = false;
1457 int deltaValue;
1458
1459 switch (mir->dalvikInsn.opcode) {
1460 case OP_ADD_INT:
1461 if (dvmIsBitSet(isConstantV,
1462 mir->ssaRep->uses[1])) {
1463 deltaValue =
1464 cUnit->constantValues[mir->ssaRep->uses[1]];
1465 deltaIsConstant = true;
1466 }
1467 break;
1468 case OP_SUB_INT:
1469 if (dvmIsBitSet(isConstantV,
1470 mir->ssaRep->uses[1])) {
1471 deltaValue =
1472 -cUnit->constantValues[mir->ssaRep->uses[1]];
1473 deltaIsConstant = true;
1474 }
1475 break;
1476 case OP_ADD_INT_LIT8:
1477 deltaValue = mir->dalvikInsn.vC;
1478 deltaIsConstant = true;
1479 break;
1480 default:
1481 break;
1482 }
1483 if (deltaIsConstant) {
1484 dvmSetBit(isIndVarV, mir->ssaRep->uses[0]);
1485 InductionVariableInfo *ivInfo = (InductionVariableInfo *)
1486 dvmCompilerNew(sizeof(InductionVariableInfo),
1487 false);
1488
1489 ivInfo->ssaReg = mir->ssaRep->uses[0];
1490 ivInfo->basicSSAReg = mir->ssaRep->uses[0];
1491 ivInfo->m = 1; // always 1 to basic iv
1492 ivInfo->c = 0; // N/A to basic iv
1493 ivInfo->inc = deltaValue;
1494 dvmInsertGrowableList(ivList, (intptr_t) ivInfo);
1495 cUnit->loopAnalysis->numBasicIV++;
1496 break;
1497 }
1498 }
1499 }
1500 }
1501
1502 /* Find dependent induction variable now */
1503 for (mir = bb->firstMIRInsn; mir; mir = mir->next) {
1504 int dfAttributes =
1505 dvmCompilerDataFlowAttributes[mir->dalvikInsn.opcode];
1506
1507 if (!(dfAttributes & DF_IS_LINEAR)) continue;
1508
1509 /* Skip already identified induction variables */
1510 if (dvmIsBitSet(isIndVarV, mir->ssaRep->defs[0])) continue;
1511
1512 /*
1513 * For a dependent induction variable:
1514 * 1) use[0] should be an induction variable (basic/dependent)
1515 * 2) operand2 should be a constant
1516 */
1517 if (dvmIsBitSet(isIndVarV, mir->ssaRep->uses[0])) {
1518 int srcDalvikReg = dvmConvertSSARegToDalvik(cUnit,
1519 mir->ssaRep->uses[0]);
1520 int dstDalvikReg = dvmConvertSSARegToDalvik(cUnit,
1521 mir->ssaRep->defs[0]);
1522
1523 bool cIsConstant = false;
1524 int c = 0;
1525
1526 switch (mir->dalvikInsn.opcode) {
1527 case OP_ADD_INT:
1528 if (dvmIsBitSet(isConstantV,
1529 mir->ssaRep->uses[1])) {
1530 c = cUnit->constantValues[mir->ssaRep->uses[1]];
1531 cIsConstant = true;
1532 }
1533 break;
1534 case OP_SUB_INT:
1535 if (dvmIsBitSet(isConstantV,
1536 mir->ssaRep->uses[1])) {
1537 c = -cUnit->constantValues[mir->ssaRep->uses[1]];
1538 cIsConstant = true;
1539 }
1540 break;
1541 case OP_ADD_INT_LIT8:
1542 c = mir->dalvikInsn.vC;
1543 cIsConstant = true;
1544 break;
1545 default:
1546 break;
1547 }
1548
1549 /* Ignore the update to the basic induction variable itself */
1550 if (DECODE_REG(srcDalvikReg) == DECODE_REG(dstDalvikReg)) {
1551 cUnit->loopAnalysis->ssaBIV = mir->ssaRep->defs[0];
1552 cIsConstant = false;
1553 }
1554
1555 if (cIsConstant) {
1556 unsigned int i;
1557 dvmSetBit(isIndVarV, mir->ssaRep->defs[0]);
1558 InductionVariableInfo *ivInfo = (InductionVariableInfo *)
1559 dvmCompilerNew(sizeof(InductionVariableInfo),
1560 false);
1561 InductionVariableInfo *ivInfoOld = NULL ;
1562
1563 for (i = 0; i < ivList->numUsed; i++) {
1564 ivInfoOld = (InductionVariableInfo *) ivList->elemList[i];
1565 if (ivInfoOld->ssaReg == mir->ssaRep->uses[0]) break;
1566 }
1567
1568 /* Guaranteed to find an element */
1569 assert(i < ivList->numUsed);
1570
1571 ivInfo->ssaReg = mir->ssaRep->defs[0];
1572 ivInfo->basicSSAReg = ivInfoOld->basicSSAReg;
1573 ivInfo->m = ivInfoOld->m;
1574 ivInfo->c = c + ivInfoOld->c;
1575 ivInfo->inc = ivInfoOld->inc;
1576 dvmInsertGrowableList(ivList, (intptr_t) ivInfo);
1577 }
1578 }
1579 }
1580 return true;
1581 }
1582
1583 /* Setup the basic data structures for SSA conversion */
dvmInitializeSSAConversion(CompilationUnit * cUnit)1584 void dvmInitializeSSAConversion(CompilationUnit *cUnit)
1585 {
1586 int i;
1587 int numDalvikReg = cUnit->method->registersSize;
1588
1589 cUnit->ssaToDalvikMap = (GrowableList *)dvmCompilerNew(sizeof(GrowableList),
1590 false);
1591 dvmInitGrowableList(cUnit->ssaToDalvikMap, numDalvikReg);
1592
1593 /*
1594 * Initial number of SSA registers is equal to the number of Dalvik
1595 * registers.
1596 */
1597 cUnit->numSSARegs = numDalvikReg;
1598
1599 /*
1600 * Initialize the SSA2Dalvik map list. For the first numDalvikReg elements,
1601 * the subscript is 0 so we use the ENCODE_REG_SUB macro to encode the value
1602 * into "(0 << 16) | i"
1603 */
1604 for (i = 0; i < numDalvikReg; i++) {
1605 dvmInsertGrowableList(cUnit->ssaToDalvikMap, ENCODE_REG_SUB(i, 0));
1606 }
1607
1608 /*
1609 * Initialize the DalvikToSSAMap map. The low 16 bit is the SSA register id,
1610 * while the high 16 bit is the current subscript. The original Dalvik
1611 * register N is mapped to SSA register N with subscript 0.
1612 */
1613 cUnit->dalvikToSSAMap = (int *)dvmCompilerNew(sizeof(int) * numDalvikReg,
1614 false);
1615 for (i = 0; i < numDalvikReg; i++) {
1616 cUnit->dalvikToSSAMap[i] = i;
1617 }
1618
1619 /*
1620 * Allocate the BasicBlockDataFlow structure for the entry and code blocks
1621 */
1622 GrowableListIterator iterator;
1623
1624 dvmGrowableListIteratorInit(&cUnit->blockList, &iterator);
1625
1626 while (true) {
1627 BasicBlock *bb = (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1628 if (bb == NULL) break;
1629 if (bb->hidden == true) continue;
1630 if (bb->blockType == kDalvikByteCode ||
1631 bb->blockType == kEntryBlock ||
1632 bb->blockType == kExitBlock) {
1633 bb->dataFlowInfo = (BasicBlockDataFlow *)
1634 dvmCompilerNew(sizeof(BasicBlockDataFlow),
1635 true);
1636 }
1637 }
1638 }
1639
1640 /* Clear the visited flag for each BB */
dvmCompilerClearVisitedFlag(struct CompilationUnit * cUnit,struct BasicBlock * bb)1641 bool dvmCompilerClearVisitedFlag(struct CompilationUnit *cUnit,
1642 struct BasicBlock *bb)
1643 {
1644 bb->visited = false;
1645 return true;
1646 }
1647
dvmCompilerDataFlowAnalysisDispatcher(CompilationUnit * cUnit,bool (* func)(CompilationUnit *,BasicBlock *),DataFlowAnalysisMode dfaMode,bool isIterative)1648 void dvmCompilerDataFlowAnalysisDispatcher(CompilationUnit *cUnit,
1649 bool (*func)(CompilationUnit *, BasicBlock *),
1650 DataFlowAnalysisMode dfaMode,
1651 bool isIterative)
1652 {
1653 bool change = true;
1654
1655 while (change) {
1656 change = false;
1657
1658 /* Scan all blocks and perform the operations specified in func */
1659 if (dfaMode == kAllNodes) {
1660 GrowableListIterator iterator;
1661 dvmGrowableListIteratorInit(&cUnit->blockList, &iterator);
1662 while (true) {
1663 BasicBlock *bb =
1664 (BasicBlock *) dvmGrowableListIteratorNext(&iterator);
1665 if (bb == NULL) break;
1666 if (bb->hidden == true) continue;
1667 change |= (*func)(cUnit, bb);
1668 }
1669 }
1670 /*
1671 * Scan all reachable blocks and perform the operations specified in
1672 * func.
1673 */
1674 else if (dfaMode == kReachableNodes) {
1675 int numReachableBlocks = cUnit->numReachableBlocks;
1676 int idx;
1677 const GrowableList *blockList = &cUnit->blockList;
1678
1679 for (idx = 0; idx < numReachableBlocks; idx++) {
1680 int blockIdx = cUnit->dfsOrder.elemList[idx];
1681 BasicBlock *bb =
1682 (BasicBlock *) dvmGrowableListGetElement(blockList,
1683 blockIdx);
1684 change |= (*func)(cUnit, bb);
1685 }
1686 }
1687 /*
1688 * Scan all reachable blocks by the pre-order in the depth-first-search
1689 * CFG and perform the operations specified in func.
1690 */
1691 else if (dfaMode == kPreOrderDFSTraversal) {
1692 int numReachableBlocks = cUnit->numReachableBlocks;
1693 int idx;
1694 const GrowableList *blockList = &cUnit->blockList;
1695
1696 for (idx = 0; idx < numReachableBlocks; idx++) {
1697 int dfsIdx = cUnit->dfsOrder.elemList[idx];
1698 BasicBlock *bb =
1699 (BasicBlock *) dvmGrowableListGetElement(blockList, dfsIdx);
1700 change |= (*func)(cUnit, bb);
1701 }
1702 }
1703 /*
1704 * Scan all reachable blocks by the post-order in the depth-first-search
1705 * CFG and perform the operations specified in func.
1706 */
1707 else if (dfaMode == kPostOrderDFSTraversal) {
1708 int numReachableBlocks = cUnit->numReachableBlocks;
1709 int idx;
1710 const GrowableList *blockList = &cUnit->blockList;
1711
1712 for (idx = numReachableBlocks - 1; idx >= 0; idx--) {
1713 int dfsIdx = cUnit->dfsOrder.elemList[idx];
1714 BasicBlock *bb =
1715 (BasicBlock *) dvmGrowableListGetElement(blockList, dfsIdx);
1716 change |= (*func)(cUnit, bb);
1717 }
1718 }
1719 /*
1720 * Scan all reachable blocks by the post-order in the dominator tree
1721 * and perform the operations specified in func.
1722 */
1723 else if (dfaMode == kPostOrderDOMTraversal) {
1724 int numReachableBlocks = cUnit->numReachableBlocks;
1725 int idx;
1726 const GrowableList *blockList = &cUnit->blockList;
1727
1728 for (idx = 0; idx < numReachableBlocks; idx++) {
1729 int domIdx = cUnit->domPostOrderTraversal.elemList[idx];
1730 BasicBlock *bb =
1731 (BasicBlock *) dvmGrowableListGetElement(blockList, domIdx);
1732 change |= (*func)(cUnit, bb);
1733 }
1734 }
1735 /* If isIterative is false, exit the loop after the first iteration */
1736 change &= isIterative;
1737 }
1738 }
1739
1740 /* Main entry point to do SSA conversion for non-loop traces */
dvmCompilerNonLoopAnalysis(CompilationUnit * cUnit)1741 void dvmCompilerNonLoopAnalysis(CompilationUnit *cUnit)
1742 {
1743 dvmCompilerDataFlowAnalysisDispatcher(cUnit, dvmCompilerDoSSAConversion,
1744 kAllNodes,
1745 false /* isIterative */);
1746 }
1747