1 /*
2 * Copyright (C) 2012 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 "local_value_numbering.h"
18
19 namespace art {
20
21
GetValueNumber(MIR * mir)22 uint16_t LocalValueNumbering::GetValueNumber(MIR* mir) {
23 uint16_t res = NO_VALUE;
24 uint16_t opcode = mir->dalvikInsn.opcode;
25 switch (opcode) {
26 case Instruction::NOP:
27 case Instruction::RETURN_VOID:
28 case Instruction::RETURN:
29 case Instruction::RETURN_OBJECT:
30 case Instruction::RETURN_WIDE:
31 case Instruction::MONITOR_ENTER:
32 case Instruction::MONITOR_EXIT:
33 case Instruction::GOTO:
34 case Instruction::GOTO_16:
35 case Instruction::GOTO_32:
36 case Instruction::CHECK_CAST:
37 case Instruction::THROW:
38 case Instruction::FILL_ARRAY_DATA:
39 case Instruction::FILLED_NEW_ARRAY:
40 case Instruction::FILLED_NEW_ARRAY_RANGE:
41 case Instruction::PACKED_SWITCH:
42 case Instruction::SPARSE_SWITCH:
43 case Instruction::IF_EQ:
44 case Instruction::IF_NE:
45 case Instruction::IF_LT:
46 case Instruction::IF_GE:
47 case Instruction::IF_GT:
48 case Instruction::IF_LE:
49 case Instruction::IF_EQZ:
50 case Instruction::IF_NEZ:
51 case Instruction::IF_LTZ:
52 case Instruction::IF_GEZ:
53 case Instruction::IF_GTZ:
54 case Instruction::IF_LEZ:
55 case Instruction::INVOKE_STATIC_RANGE:
56 case Instruction::INVOKE_STATIC:
57 case Instruction::INVOKE_DIRECT:
58 case Instruction::INVOKE_DIRECT_RANGE:
59 case Instruction::INVOKE_VIRTUAL:
60 case Instruction::INVOKE_VIRTUAL_RANGE:
61 case Instruction::INVOKE_SUPER:
62 case Instruction::INVOKE_SUPER_RANGE:
63 case Instruction::INVOKE_INTERFACE:
64 case Instruction::INVOKE_INTERFACE_RANGE:
65 case kMirOpFusedCmplFloat:
66 case kMirOpFusedCmpgFloat:
67 case kMirOpFusedCmplDouble:
68 case kMirOpFusedCmpgDouble:
69 case kMirOpFusedCmpLong:
70 // Nothing defined - take no action.
71 break;
72
73 case Instruction::MOVE_EXCEPTION:
74 case Instruction::MOVE_RESULT:
75 case Instruction::MOVE_RESULT_OBJECT:
76 case Instruction::INSTANCE_OF:
77 case Instruction::NEW_INSTANCE:
78 case Instruction::CONST_STRING:
79 case Instruction::CONST_STRING_JUMBO:
80 case Instruction::CONST_CLASS:
81 case Instruction::NEW_ARRAY: {
82 // 1 result, treat as unique each time, use result s_reg - will be unique.
83 uint16_t res = GetOperandValue(mir->ssa_rep->defs[0]);
84 SetOperandValue(mir->ssa_rep->defs[0], res);
85 }
86 break;
87 case Instruction::MOVE_RESULT_WIDE: {
88 // 1 wide result, treat as unique each time, use result s_reg - will be unique.
89 uint16_t res = GetOperandValueWide(mir->ssa_rep->defs[0]);
90 SetOperandValueWide(mir->ssa_rep->defs[0], res);
91 }
92 break;
93
94 case kMirOpPhi:
95 /*
96 * Because we'll only see phi nodes at the beginning of an extended basic block,
97 * we can ignore them. Revisit if we shift to global value numbering.
98 */
99 break;
100
101 case Instruction::MOVE:
102 case Instruction::MOVE_OBJECT:
103 case Instruction::MOVE_16:
104 case Instruction::MOVE_OBJECT_16:
105 case Instruction::MOVE_FROM16:
106 case Instruction::MOVE_OBJECT_FROM16:
107 case kMirOpCopy: {
108 // Just copy value number of source to value number of resulit.
109 uint16_t res = GetOperandValue(mir->ssa_rep->uses[0]);
110 SetOperandValue(mir->ssa_rep->defs[0], res);
111 }
112 break;
113
114 case Instruction::MOVE_WIDE:
115 case Instruction::MOVE_WIDE_16:
116 case Instruction::MOVE_WIDE_FROM16: {
117 // Just copy value number of source to value number of result.
118 uint16_t res = GetOperandValueWide(mir->ssa_rep->uses[0]);
119 SetOperandValueWide(mir->ssa_rep->defs[0], res);
120 }
121 break;
122
123 case Instruction::CONST:
124 case Instruction::CONST_4:
125 case Instruction::CONST_16: {
126 uint16_t res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
127 High16Bits(mir->dalvikInsn.vB >> 16), 0);
128 SetOperandValue(mir->ssa_rep->defs[0], res);
129 }
130 break;
131
132 case Instruction::CONST_HIGH16: {
133 uint16_t res = LookupValue(Instruction::CONST, 0, mir->dalvikInsn.vB, 0);
134 SetOperandValue(mir->ssa_rep->defs[0], res);
135 }
136 break;
137
138 case Instruction::CONST_WIDE_16:
139 case Instruction::CONST_WIDE_32: {
140 uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(mir->dalvikInsn.vB),
141 High16Bits(mir->dalvikInsn.vB >> 16), 1);
142 uint16_t high_res;
143 if (mir->dalvikInsn.vB & 0x80000000) {
144 high_res = LookupValue(Instruction::CONST, 0xffff, 0xffff, 2);
145 } else {
146 high_res = LookupValue(Instruction::CONST, 0, 0, 2);
147 }
148 uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3);
149 SetOperandValue(mir->ssa_rep->defs[0], res);
150 }
151 break;
152
153 case Instruction::CONST_WIDE: {
154 uint32_t low_word = Low32Bits(mir->dalvikInsn.vB_wide);
155 uint32_t high_word = High32Bits(mir->dalvikInsn.vB_wide);
156 uint16_t low_res = LookupValue(Instruction::CONST, Low16Bits(low_word),
157 High16Bits(low_word), 1);
158 uint16_t high_res = LookupValue(Instruction::CONST, Low16Bits(high_word),
159 High16Bits(high_word), 2);
160 uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3);
161 SetOperandValueWide(mir->ssa_rep->defs[0], res);
162 }
163 break;
164
165 case Instruction::CONST_WIDE_HIGH16: {
166 uint16_t low_res = LookupValue(Instruction::CONST, 0, 0, 1);
167 uint16_t high_res = LookupValue(Instruction::CONST, 0, Low16Bits(mir->dalvikInsn.vB), 2);
168 uint16_t res = LookupValue(Instruction::CONST, low_res, high_res, 3);
169 SetOperandValueWide(mir->ssa_rep->defs[0], res);
170 }
171 break;
172
173 case Instruction::ARRAY_LENGTH:
174 case Instruction::NEG_INT:
175 case Instruction::NOT_INT:
176 case Instruction::NEG_FLOAT:
177 case Instruction::INT_TO_BYTE:
178 case Instruction::INT_TO_SHORT:
179 case Instruction::INT_TO_CHAR:
180 case Instruction::INT_TO_FLOAT:
181 case Instruction::FLOAT_TO_INT: {
182 // res = op + 1 operand
183 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
184 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
185 SetOperandValue(mir->ssa_rep->defs[0], res);
186 }
187 break;
188
189 case Instruction::LONG_TO_FLOAT:
190 case Instruction::LONG_TO_INT:
191 case Instruction::DOUBLE_TO_FLOAT:
192 case Instruction::DOUBLE_TO_INT: {
193 // res = op + 1 wide operand
194 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
195 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
196 SetOperandValue(mir->ssa_rep->defs[0], res);
197 }
198 break;
199
200
201 case Instruction::DOUBLE_TO_LONG:
202 case Instruction::LONG_TO_DOUBLE:
203 case Instruction::NEG_LONG:
204 case Instruction::NOT_LONG:
205 case Instruction::NEG_DOUBLE: {
206 // wide res = op + 1 wide operand
207 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
208 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
209 SetOperandValueWide(mir->ssa_rep->defs[0], res);
210 }
211 break;
212
213 case Instruction::FLOAT_TO_DOUBLE:
214 case Instruction::FLOAT_TO_LONG:
215 case Instruction::INT_TO_DOUBLE:
216 case Instruction::INT_TO_LONG: {
217 // wide res = op + 1 operand
218 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
219 uint16_t res = LookupValue(opcode, operand1, NO_VALUE, NO_VALUE);
220 SetOperandValueWide(mir->ssa_rep->defs[0], res);
221 }
222 break;
223
224 case Instruction::CMPL_DOUBLE:
225 case Instruction::CMPG_DOUBLE:
226 case Instruction::CMP_LONG: {
227 // res = op + 2 wide operands
228 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
229 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
230 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
231 SetOperandValue(mir->ssa_rep->defs[0], res);
232 }
233 break;
234
235 case Instruction::CMPG_FLOAT:
236 case Instruction::CMPL_FLOAT:
237 case Instruction::ADD_INT:
238 case Instruction::ADD_INT_2ADDR:
239 case Instruction::MUL_INT:
240 case Instruction::MUL_INT_2ADDR:
241 case Instruction::AND_INT:
242 case Instruction::AND_INT_2ADDR:
243 case Instruction::OR_INT:
244 case Instruction::OR_INT_2ADDR:
245 case Instruction::XOR_INT:
246 case Instruction::XOR_INT_2ADDR:
247 case Instruction::SUB_INT:
248 case Instruction::SUB_INT_2ADDR:
249 case Instruction::DIV_INT:
250 case Instruction::DIV_INT_2ADDR:
251 case Instruction::REM_INT:
252 case Instruction::REM_INT_2ADDR:
253 case Instruction::SHL_INT:
254 case Instruction::SHL_INT_2ADDR:
255 case Instruction::SHR_INT:
256 case Instruction::SHR_INT_2ADDR:
257 case Instruction::USHR_INT:
258 case Instruction::USHR_INT_2ADDR: {
259 // res = op + 2 operands
260 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
261 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]);
262 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
263 SetOperandValue(mir->ssa_rep->defs[0], res);
264 }
265 break;
266
267 case Instruction::ADD_LONG:
268 case Instruction::SUB_LONG:
269 case Instruction::MUL_LONG:
270 case Instruction::DIV_LONG:
271 case Instruction::REM_LONG:
272 case Instruction::AND_LONG:
273 case Instruction::OR_LONG:
274 case Instruction::XOR_LONG:
275 case Instruction::ADD_LONG_2ADDR:
276 case Instruction::SUB_LONG_2ADDR:
277 case Instruction::MUL_LONG_2ADDR:
278 case Instruction::DIV_LONG_2ADDR:
279 case Instruction::REM_LONG_2ADDR:
280 case Instruction::AND_LONG_2ADDR:
281 case Instruction::OR_LONG_2ADDR:
282 case Instruction::XOR_LONG_2ADDR:
283 case Instruction::ADD_DOUBLE:
284 case Instruction::SUB_DOUBLE:
285 case Instruction::MUL_DOUBLE:
286 case Instruction::DIV_DOUBLE:
287 case Instruction::REM_DOUBLE:
288 case Instruction::ADD_DOUBLE_2ADDR:
289 case Instruction::SUB_DOUBLE_2ADDR:
290 case Instruction::MUL_DOUBLE_2ADDR:
291 case Instruction::DIV_DOUBLE_2ADDR:
292 case Instruction::REM_DOUBLE_2ADDR: {
293 // wide res = op + 2 wide operands
294 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
295 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
296 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
297 SetOperandValueWide(mir->ssa_rep->defs[0], res);
298 }
299 break;
300
301 case Instruction::SHL_LONG:
302 case Instruction::SHR_LONG:
303 case Instruction::USHR_LONG:
304 case Instruction::SHL_LONG_2ADDR:
305 case Instruction::SHR_LONG_2ADDR:
306 case Instruction::USHR_LONG_2ADDR: {
307 // wide res = op + 1 wide operand + 1 operand
308 uint16_t operand1 = GetOperandValueWide(mir->ssa_rep->uses[0]);
309 uint16_t operand2 = GetOperandValueWide(mir->ssa_rep->uses[2]);
310 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
311 SetOperandValueWide(mir->ssa_rep->defs[0], res);
312 }
313 break;
314
315 case Instruction::ADD_FLOAT:
316 case Instruction::SUB_FLOAT:
317 case Instruction::MUL_FLOAT:
318 case Instruction::DIV_FLOAT:
319 case Instruction::REM_FLOAT:
320 case Instruction::ADD_FLOAT_2ADDR:
321 case Instruction::SUB_FLOAT_2ADDR:
322 case Instruction::MUL_FLOAT_2ADDR:
323 case Instruction::DIV_FLOAT_2ADDR:
324 case Instruction::REM_FLOAT_2ADDR: {
325 // res = op + 2 operands
326 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
327 uint16_t operand2 = GetOperandValue(mir->ssa_rep->uses[1]);
328 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
329 SetOperandValue(mir->ssa_rep->defs[0], res);
330 }
331 break;
332
333 case Instruction::RSUB_INT:
334 case Instruction::ADD_INT_LIT16:
335 case Instruction::MUL_INT_LIT16:
336 case Instruction::DIV_INT_LIT16:
337 case Instruction::REM_INT_LIT16:
338 case Instruction::AND_INT_LIT16:
339 case Instruction::OR_INT_LIT16:
340 case Instruction::XOR_INT_LIT16:
341 case Instruction::ADD_INT_LIT8:
342 case Instruction::RSUB_INT_LIT8:
343 case Instruction::MUL_INT_LIT8:
344 case Instruction::DIV_INT_LIT8:
345 case Instruction::REM_INT_LIT8:
346 case Instruction::AND_INT_LIT8:
347 case Instruction::OR_INT_LIT8:
348 case Instruction::XOR_INT_LIT8:
349 case Instruction::SHL_INT_LIT8:
350 case Instruction::SHR_INT_LIT8:
351 case Instruction::USHR_INT_LIT8: {
352 // Same as res = op + 2 operands, except use vB as operand 2
353 uint16_t operand1 = GetOperandValue(mir->ssa_rep->uses[0]);
354 uint16_t operand2 = LookupValue(Instruction::CONST, mir->dalvikInsn.vB, 0, 0);
355 uint16_t res = LookupValue(opcode, operand1, operand2, NO_VALUE);
356 SetOperandValue(mir->ssa_rep->defs[0], res);
357 }
358 break;
359
360 case Instruction::AGET_WIDE:
361 case Instruction::AGET:
362 case Instruction::AGET_OBJECT:
363 case Instruction::AGET_BOOLEAN:
364 case Instruction::AGET_BYTE:
365 case Instruction::AGET_CHAR:
366 case Instruction::AGET_SHORT: {
367 uint16_t array = GetOperandValue(mir->ssa_rep->uses[0]);
368 if (null_checked_.find(array) != null_checked_.end()) {
369 if (cu_->verbose) {
370 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
371 }
372 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
373 } else {
374 null_checked_.insert(array);
375 }
376 uint16_t index = GetOperandValue(mir->ssa_rep->uses[1]);
377 if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) {
378 if (cu_->verbose) {
379 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
380 }
381 mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
382 }
383 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
384 // Use side effect to note range check completed.
385 (void)LookupValue(ARRAY_REF, array, index, NO_VALUE);
386 // Establish value number for loaded register. Note use of memory version.
387 uint16_t memory_version = GetMemoryVersion(array, NO_VALUE);
388 uint16_t res = LookupValue(ARRAY_REF, array, index, memory_version);
389 if (opcode == Instruction::AGET_WIDE) {
390 SetOperandValueWide(mir->ssa_rep->defs[0], res);
391 } else {
392 SetOperandValue(mir->ssa_rep->defs[0], res);
393 }
394 }
395 break;
396
397 case Instruction::APUT_WIDE:
398 case Instruction::APUT:
399 case Instruction::APUT_OBJECT:
400 case Instruction::APUT_SHORT:
401 case Instruction::APUT_CHAR:
402 case Instruction::APUT_BYTE:
403 case Instruction::APUT_BOOLEAN: {
404 int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1;
405 int index_idx = array_idx + 1;
406 uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]);
407 if (null_checked_.find(array) != null_checked_.end()) {
408 if (cu_->verbose) {
409 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
410 }
411 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
412 } else {
413 null_checked_.insert(array);
414 }
415 uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]);
416 if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) {
417 if (cu_->verbose) {
418 LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
419 }
420 mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
421 }
422 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
423 // Use side effect to note range check completed.
424 (void)LookupValue(ARRAY_REF, array, index, NO_VALUE);
425 // Rev the memory version
426 AdvanceMemoryVersion(array, NO_VALUE);
427 }
428 break;
429
430 case Instruction::IGET_OBJECT:
431 case Instruction::IGET_WIDE:
432 case Instruction::IGET:
433 case Instruction::IGET_CHAR:
434 case Instruction::IGET_SHORT:
435 case Instruction::IGET_BOOLEAN:
436 case Instruction::IGET_BYTE: {
437 uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]);
438 if (null_checked_.find(base) != null_checked_.end()) {
439 if (cu_->verbose) {
440 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
441 }
442 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
443 } else {
444 null_checked_.insert(base);
445 }
446 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
447 uint16_t field_ref = mir->dalvikInsn.vC;
448 uint16_t memory_version = GetMemoryVersion(base, field_ref);
449 if (opcode == Instruction::IGET_WIDE) {
450 uint16_t res = LookupValue(Instruction::IGET_WIDE, base, field_ref, memory_version);
451 SetOperandValueWide(mir->ssa_rep->defs[0], res);
452 } else {
453 uint16_t res = LookupValue(Instruction::IGET, base, field_ref, memory_version);
454 SetOperandValue(mir->ssa_rep->defs[0], res);
455 }
456 }
457 break;
458
459 case Instruction::IPUT_WIDE:
460 case Instruction::IPUT_OBJECT:
461 case Instruction::IPUT:
462 case Instruction::IPUT_BOOLEAN:
463 case Instruction::IPUT_BYTE:
464 case Instruction::IPUT_CHAR:
465 case Instruction::IPUT_SHORT: {
466 int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1;
467 uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]);
468 if (null_checked_.find(base) != null_checked_.end()) {
469 if (cu_->verbose) {
470 LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
471 }
472 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
473 } else {
474 null_checked_.insert(base);
475 }
476 mir->meta.throw_insn->optimization_flags |= mir->optimization_flags;
477 uint16_t field_ref = mir->dalvikInsn.vC;
478 AdvanceMemoryVersion(base, field_ref);
479 }
480 break;
481
482 case Instruction::SGET_OBJECT:
483 case Instruction::SGET:
484 case Instruction::SGET_BOOLEAN:
485 case Instruction::SGET_BYTE:
486 case Instruction::SGET_CHAR:
487 case Instruction::SGET_SHORT:
488 case Instruction::SGET_WIDE: {
489 uint16_t field_ref = mir->dalvikInsn.vB;
490 uint16_t memory_version = GetMemoryVersion(NO_VALUE, field_ref);
491 if (opcode == Instruction::SGET_WIDE) {
492 uint16_t res = LookupValue(Instruction::SGET_WIDE, NO_VALUE, field_ref, memory_version);
493 SetOperandValueWide(mir->ssa_rep->defs[0], res);
494 } else {
495 uint16_t res = LookupValue(Instruction::SGET, NO_VALUE, field_ref, memory_version);
496 SetOperandValue(mir->ssa_rep->defs[0], res);
497 }
498 }
499 break;
500
501 case Instruction::SPUT_OBJECT:
502 case Instruction::SPUT:
503 case Instruction::SPUT_BOOLEAN:
504 case Instruction::SPUT_BYTE:
505 case Instruction::SPUT_CHAR:
506 case Instruction::SPUT_SHORT:
507 case Instruction::SPUT_WIDE: {
508 uint16_t field_ref = mir->dalvikInsn.vB;
509 AdvanceMemoryVersion(NO_VALUE, field_ref);
510 }
511 break;
512 }
513 return res;
514 }
515
516 } // namespace art
517