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