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
19namespace art {
20
21
22uint16_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