local_value_numbering.cc revision 8a3e7e769de02b5b412163cf70da9b9fbaf3b848 
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        // Use side effect to note range check completed.
384        (void)LookupValue(ARRAY_REF, array, index, NO_VALUE);
385        // Establish value number for loaded register. Note use of memory version.
386        uint16_t memory_version = GetMemoryVersion(array, NO_VALUE);
387        uint16_t res = LookupValue(ARRAY_REF, array, index, memory_version);
388        if (opcode == Instruction::AGET_WIDE) {
389          SetOperandValueWide(mir->ssa_rep->defs[0], res);
390        } else {
391          SetOperandValue(mir->ssa_rep->defs[0], res);
392        }
393      }
394      break;
395
396    case Instruction::APUT_WIDE:
397    case Instruction::APUT:
398    case Instruction::APUT_OBJECT:
399    case Instruction::APUT_SHORT:
400    case Instruction::APUT_CHAR:
401    case Instruction::APUT_BYTE:
402    case Instruction::APUT_BOOLEAN: {
403        int array_idx = (opcode == Instruction::APUT_WIDE) ? 2 : 1;
404        int index_idx = array_idx + 1;
405        uint16_t array = GetOperandValue(mir->ssa_rep->uses[array_idx]);
406        if (null_checked_.find(array) != null_checked_.end()) {
407          if (cu_->verbose) {
408            LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
409          }
410          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
411        } else {
412          null_checked_.insert(array);
413        }
414        uint16_t index = GetOperandValue(mir->ssa_rep->uses[index_idx]);
415        if (ValueExists(ARRAY_REF, array, index, NO_VALUE)) {
416          if (cu_->verbose) {
417            LOG(INFO) << "Removing range check for 0x" << std::hex << mir->offset;
418          }
419          mir->optimization_flags |= MIR_IGNORE_RANGE_CHECK;
420        }
421        // Use side effect to note range check completed.
422        (void)LookupValue(ARRAY_REF, array, index, NO_VALUE);
423        // Rev the memory version
424        AdvanceMemoryVersion(array, NO_VALUE);
425      }
426      break;
427
428    case Instruction::IGET_OBJECT:
429    case Instruction::IGET_WIDE:
430    case Instruction::IGET:
431    case Instruction::IGET_CHAR:
432    case Instruction::IGET_SHORT:
433    case Instruction::IGET_BOOLEAN:
434    case Instruction::IGET_BYTE: {
435        uint16_t base = GetOperandValue(mir->ssa_rep->uses[0]);
436        if (null_checked_.find(base) != null_checked_.end()) {
437          if (cu_->verbose) {
438            LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
439          }
440          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
441        } else {
442          null_checked_.insert(base);
443        }
444        uint16_t field_ref = mir->dalvikInsn.vC;
445        uint16_t memory_version = GetMemoryVersion(base, field_ref);
446        if (opcode == Instruction::IGET_WIDE) {
447          uint16_t res = LookupValue(Instruction::IGET_WIDE, base, field_ref, memory_version);
448          SetOperandValueWide(mir->ssa_rep->defs[0], res);
449        } else {
450          uint16_t res = LookupValue(Instruction::IGET, base, field_ref, memory_version);
451          SetOperandValue(mir->ssa_rep->defs[0], res);
452        }
453      }
454      break;
455
456    case Instruction::IPUT_WIDE:
457    case Instruction::IPUT_OBJECT:
458    case Instruction::IPUT:
459    case Instruction::IPUT_BOOLEAN:
460    case Instruction::IPUT_BYTE:
461    case Instruction::IPUT_CHAR:
462    case Instruction::IPUT_SHORT: {
463        int base_reg = (opcode == Instruction::IPUT_WIDE) ? 2 : 1;
464        uint16_t base = GetOperandValue(mir->ssa_rep->uses[base_reg]);
465        if (null_checked_.find(base) != null_checked_.end()) {
466          if (cu_->verbose) {
467            LOG(INFO) << "Removing null check for 0x" << std::hex << mir->offset;
468          }
469          mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
470        } else {
471          null_checked_.insert(base);
472        }
473        uint16_t field_ref = mir->dalvikInsn.vC;
474        AdvanceMemoryVersion(base, field_ref);
475      }
476      break;
477
478    case Instruction::SGET_OBJECT:
479    case Instruction::SGET:
480    case Instruction::SGET_BOOLEAN:
481    case Instruction::SGET_BYTE:
482    case Instruction::SGET_CHAR:
483    case Instruction::SGET_SHORT:
484    case Instruction::SGET_WIDE: {
485        uint16_t field_ref = mir->dalvikInsn.vB;
486        uint16_t memory_version = GetMemoryVersion(NO_VALUE, field_ref);
487        if (opcode == Instruction::SGET_WIDE) {
488          uint16_t res = LookupValue(Instruction::SGET_WIDE, NO_VALUE, field_ref, memory_version);
489          SetOperandValueWide(mir->ssa_rep->defs[0], res);
490        } else {
491          uint16_t res = LookupValue(Instruction::SGET, NO_VALUE, field_ref, memory_version);
492          SetOperandValue(mir->ssa_rep->defs[0], res);
493        }
494      }
495      break;
496
497    case Instruction::SPUT_OBJECT:
498    case Instruction::SPUT:
499    case Instruction::SPUT_BOOLEAN:
500    case Instruction::SPUT_BYTE:
501    case Instruction::SPUT_CHAR:
502    case Instruction::SPUT_SHORT:
503    case Instruction::SPUT_WIDE: {
504        uint16_t field_ref = mir->dalvikInsn.vB;
505        AdvanceMemoryVersion(NO_VALUE, field_ref);
506      }
507      break;
508  }
509  return res;
510}
511
512}    // namespace art
513