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