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