blob: 759dc328ef3f93e3604211af78cf216193599a62 [file] [log] [blame]
buzbee311ca162013-02-28 15:56:43 -08001/*
2 * Copyright (C) 2011 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 "compiler_internals.h"
18#include "local_value_numbering.h"
19#include "dataflow_iterator.h"
20
21namespace art {
22
23static unsigned int Predecessors(BasicBlock* bb)
24{
25 return bb->predecessors->num_used;
26}
27
28/* Setup a constant value for opcodes thare have the DF_SETS_CONST attribute */
29void MIRGraph::SetConstant(int32_t ssa_reg, int value)
30{
31 SetBit(cu_, is_constant_v_, ssa_reg);
32 constant_values_[ssa_reg] = value;
33}
34
35void MIRGraph::SetConstantWide(int ssa_reg, int64_t value)
36{
37 SetBit(cu_, is_constant_v_, ssa_reg);
38 constant_values_[ssa_reg] = Low32Bits(value);
39 constant_values_[ssa_reg + 1] = High32Bits(value);
40}
41
42bool MIRGraph::DoConstantPropogation(BasicBlock* bb)
43{
44 MIR* mir;
45 ArenaBitVector *is_constant_v = is_constant_v_;
46
47 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
48 int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
49
50 DecodedInstruction *d_insn = &mir->dalvikInsn;
51
52 if (!(df_attributes & DF_HAS_DEFS)) continue;
53
54 /* Handle instructions that set up constants directly */
55 if (df_attributes & DF_SETS_CONST) {
56 if (df_attributes & DF_DA) {
57 int32_t vB = static_cast<int32_t>(d_insn->vB);
58 switch (d_insn->opcode) {
59 case Instruction::CONST_4:
60 case Instruction::CONST_16:
61 case Instruction::CONST:
62 SetConstant(mir->ssa_rep->defs[0], vB);
63 break;
64 case Instruction::CONST_HIGH16:
65 SetConstant(mir->ssa_rep->defs[0], vB << 16);
66 break;
67 case Instruction::CONST_WIDE_16:
68 case Instruction::CONST_WIDE_32:
69 SetConstantWide(mir->ssa_rep->defs[0], static_cast<int64_t>(vB));
70 break;
71 case Instruction::CONST_WIDE:
72 SetConstantWide(mir->ssa_rep->defs[0],d_insn->vB_wide);
73 break;
74 case Instruction::CONST_WIDE_HIGH16:
75 SetConstantWide(mir->ssa_rep->defs[0], static_cast<int64_t>(vB) << 48);
76 break;
77 default:
78 break;
79 }
80 }
81 /* Handle instructions that set up constants directly */
82 } else if (df_attributes & DF_IS_MOVE) {
83 int i;
84
85 for (i = 0; i < mir->ssa_rep->num_uses; i++) {
86 if (!IsBitSet(is_constant_v, mir->ssa_rep->uses[i])) break;
87 }
88 /* Move a register holding a constant to another register */
89 if (i == mir->ssa_rep->num_uses) {
90 SetConstant(mir->ssa_rep->defs[0], constant_values_[mir->ssa_rep->uses[0]]);
91 if (df_attributes & DF_A_WIDE) {
92 SetConstant(mir->ssa_rep->defs[1], constant_values_[mir->ssa_rep->uses[1]]);
93 }
94 }
95 }
96 }
97 /* TODO: implement code to handle arithmetic operations */
98 return true;
99}
100
101void MIRGraph::PropagateConstants()
102{
103 is_constant_v_ = AllocBitVector(cu_, GetNumSSARegs(), false);
104 constant_values_ = static_cast<int*>(NewMem(cu_, sizeof(int) * GetNumSSARegs(), true,
105 kAllocDFInfo));
buzbee0665fe02013-03-21 12:32:21 -0700106 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800107 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
108 DoConstantPropogation(bb);
109 }
110
111}
112
113/* Advance to next strictly dominated MIR node in an extended basic block */
114static MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir)
115{
116 BasicBlock* bb = *p_bb;
117 if (mir != NULL) {
118 mir = mir->next;
119 if (mir == NULL) {
120 bb = bb->fall_through;
121 if ((bb == NULL) || Predecessors(bb) != 1) {
122 mir = NULL;
123 } else {
124 *p_bb = bb;
125 mir = bb->first_mir_insn;
126 }
127 }
128 }
129 return mir;
130}
131
132/*
133 * To be used at an invoke mir. If the logically next mir node represents
134 * a move-result, return it. Else, return NULL. If a move-result exists,
135 * it is required to immediately follow the invoke with no intervening
136 * opcodes or incoming arcs. However, if the result of the invoke is not
137 * used, a move-result may not be present.
138 */
139MIR* MIRGraph::FindMoveResult(BasicBlock* bb, MIR* mir)
140{
141 BasicBlock* tbb = bb;
142 mir = AdvanceMIR(&tbb, mir);
143 while (mir != NULL) {
144 int opcode = mir->dalvikInsn.opcode;
145 if ((mir->dalvikInsn.opcode == Instruction::MOVE_RESULT) ||
146 (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) ||
147 (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_WIDE)) {
148 break;
149 }
150 // Keep going if pseudo op, otherwise terminate
151 if (opcode < kNumPackedOpcodes) {
152 mir = NULL;
153 } else {
154 mir = AdvanceMIR(&tbb, mir);
155 }
156 }
157 return mir;
158}
159
160static BasicBlock* NextDominatedBlock(BasicBlock* bb)
161{
162 if (bb->block_type == kDead) {
163 return NULL;
164 }
165 DCHECK((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
166 || (bb->block_type == kExitBlock));
167 bb = bb->fall_through;
168 if (bb == NULL || (Predecessors(bb) != 1)) {
169 return NULL;
170 }
171 DCHECK((bb->block_type == kDalvikByteCode) || (bb->block_type == kExitBlock));
172 return bb;
173}
174
175static MIR* FindPhi(BasicBlock* bb, int ssa_name)
176{
177 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
178 if (static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi) {
179 for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
180 if (mir->ssa_rep->uses[i] == ssa_name) {
181 return mir;
182 }
183 }
184 }
185 }
186 return NULL;
187}
188
189static SelectInstructionKind SelectKind(MIR* mir)
190{
191 switch (mir->dalvikInsn.opcode) {
192 case Instruction::MOVE:
193 case Instruction::MOVE_OBJECT:
194 case Instruction::MOVE_16:
195 case Instruction::MOVE_OBJECT_16:
196 case Instruction::MOVE_FROM16:
197 case Instruction::MOVE_OBJECT_FROM16:
198 return kSelectMove;
199 case Instruction::CONST:
200 case Instruction::CONST_4:
201 case Instruction::CONST_16:
202 return kSelectConst;
203 case Instruction::GOTO:
204 case Instruction::GOTO_16:
205 case Instruction::GOTO_32:
206 return kSelectGoto;
207 default:;
208 }
209 return kSelectNone;
210}
211
212int MIRGraph::GetSSAUseCount(int s_reg)
213{
214 DCHECK(s_reg < static_cast<int>(raw_use_counts_.num_used));
215 return raw_use_counts_.elem_list[s_reg];
216}
217
218
219/* Do some MIR-level extended basic block optimizations */
220bool MIRGraph::BasicBlockOpt(BasicBlock* bb)
221{
222 if (bb->block_type == kDead) {
223 return true;
224 }
225 int num_temps = 0;
226 LocalValueNumbering local_valnum(cu_);
227 while (bb != NULL) {
228 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
229 // TUNING: use the returned value number for CSE.
230 local_valnum.GetValueNumber(mir);
231 // Look for interesting opcodes, skip otherwise
232 Instruction::Code opcode = mir->dalvikInsn.opcode;
233 switch (opcode) {
234 case Instruction::CMPL_FLOAT:
235 case Instruction::CMPL_DOUBLE:
236 case Instruction::CMPG_FLOAT:
237 case Instruction::CMPG_DOUBLE:
238 case Instruction::CMP_LONG:
239 if (cu_->gen_bitcode) {
240 // Bitcode doesn't allow this optimization.
241 break;
242 }
243 if (mir->next != NULL) {
244 MIR* mir_next = mir->next;
245 Instruction::Code br_opcode = mir_next->dalvikInsn.opcode;
246 ConditionCode ccode = kCondNv;
247 switch(br_opcode) {
248 case Instruction::IF_EQZ:
249 ccode = kCondEq;
250 break;
251 case Instruction::IF_NEZ:
252 ccode = kCondNe;
253 break;
254 case Instruction::IF_LTZ:
255 ccode = kCondLt;
256 break;
257 case Instruction::IF_GEZ:
258 ccode = kCondGe;
259 break;
260 case Instruction::IF_GTZ:
261 ccode = kCondGt;
262 break;
263 case Instruction::IF_LEZ:
264 ccode = kCondLe;
265 break;
266 default:
267 break;
268 }
269 // Make sure result of cmp is used by next insn and nowhere else
270 if ((ccode != kCondNv) &&
271 (mir->ssa_rep->defs[0] == mir_next->ssa_rep->uses[0]) &&
272 (GetSSAUseCount(mir->ssa_rep->defs[0]) == 1)) {
273 mir_next->dalvikInsn.arg[0] = ccode;
274 switch(opcode) {
275 case Instruction::CMPL_FLOAT:
276 mir_next->dalvikInsn.opcode =
277 static_cast<Instruction::Code>(kMirOpFusedCmplFloat);
278 break;
279 case Instruction::CMPL_DOUBLE:
280 mir_next->dalvikInsn.opcode =
281 static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
282 break;
283 case Instruction::CMPG_FLOAT:
284 mir_next->dalvikInsn.opcode =
285 static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
286 break;
287 case Instruction::CMPG_DOUBLE:
288 mir_next->dalvikInsn.opcode =
289 static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
290 break;
291 case Instruction::CMP_LONG:
292 mir_next->dalvikInsn.opcode =
293 static_cast<Instruction::Code>(kMirOpFusedCmpLong);
294 break;
295 default: LOG(ERROR) << "Unexpected opcode: " << opcode;
296 }
297 mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
298 mir_next->ssa_rep->num_uses = mir->ssa_rep->num_uses;
299 mir_next->ssa_rep->uses = mir->ssa_rep->uses;
300 mir_next->ssa_rep->fp_use = mir->ssa_rep->fp_use;
301 mir_next->ssa_rep->num_defs = 0;
302 mir->ssa_rep->num_uses = 0;
303 mir->ssa_rep->num_defs = 0;
304 }
305 }
306 break;
307 case Instruction::GOTO:
308 case Instruction::GOTO_16:
309 case Instruction::GOTO_32:
310 case Instruction::IF_EQ:
311 case Instruction::IF_NE:
312 case Instruction::IF_LT:
313 case Instruction::IF_GE:
314 case Instruction::IF_GT:
315 case Instruction::IF_LE:
316 case Instruction::IF_EQZ:
317 case Instruction::IF_NEZ:
318 case Instruction::IF_LTZ:
319 case Instruction::IF_GEZ:
320 case Instruction::IF_GTZ:
321 case Instruction::IF_LEZ:
322 if (bb->taken->dominates_return) {
323 mir->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
324 if (cu_->verbose) {
325 LOG(INFO) << "Suppressed suspend check on branch to return at 0x" << std::hex << mir->offset;
326 }
327 }
328 break;
329 default:
330 break;
331 }
332 // Is this the select pattern?
333 // TODO: flesh out support for Mips and X86. NOTE: llvm's select op doesn't quite work here.
334 // TUNING: expand to support IF_xx compare & branches
335 if (!cu_->gen_bitcode && (cu_->instruction_set == kThumb2) &&
336 ((mir->dalvikInsn.opcode == Instruction::IF_EQZ) ||
337 (mir->dalvikInsn.opcode == Instruction::IF_NEZ))) {
338 BasicBlock* ft = bb->fall_through;
339 DCHECK(ft != NULL);
340 BasicBlock* ft_ft = ft->fall_through;
341 BasicBlock* ft_tk = ft->taken;
342
343 BasicBlock* tk = bb->taken;
344 DCHECK(tk != NULL);
345 BasicBlock* tk_ft = tk->fall_through;
346 BasicBlock* tk_tk = tk->taken;
347
348 /*
349 * In the select pattern, the taken edge goes to a block that unconditionally
350 * transfers to the rejoin block and the fall_though edge goes to a block that
351 * unconditionally falls through to the rejoin block.
352 */
353 if ((tk_ft == NULL) && (ft_tk == NULL) && (tk_tk == ft_ft) &&
354 (Predecessors(tk) == 1) && (Predecessors(ft) == 1)) {
355 /*
356 * Okay - we have the basic diamond shape. At the very least, we can eliminate the
357 * suspend check on the taken-taken branch back to the join point.
358 */
359 if (SelectKind(tk->last_mir_insn) == kSelectGoto) {
360 tk->last_mir_insn->optimization_flags |= (MIR_IGNORE_SUSPEND_CHECK);
361 }
362 // Are the block bodies something we can handle?
363 if ((ft->first_mir_insn == ft->last_mir_insn) &&
364 (tk->first_mir_insn != tk->last_mir_insn) &&
365 (tk->first_mir_insn->next == tk->last_mir_insn) &&
366 ((SelectKind(ft->first_mir_insn) == kSelectMove) ||
367 (SelectKind(ft->first_mir_insn) == kSelectConst)) &&
368 (SelectKind(ft->first_mir_insn) == SelectKind(tk->first_mir_insn)) &&
369 (SelectKind(tk->last_mir_insn) == kSelectGoto)) {
370 // Almost there. Are the instructions targeting the same vreg?
371 MIR* if_true = tk->first_mir_insn;
372 MIR* if_false = ft->first_mir_insn;
373 // It's possible that the target of the select isn't used - skip those (rare) cases.
374 MIR* phi = FindPhi(tk_tk, if_true->ssa_rep->defs[0]);
375 if ((phi != NULL) && (if_true->dalvikInsn.vA == if_false->dalvikInsn.vA)) {
376 /*
377 * We'll convert the IF_EQZ/IF_NEZ to a SELECT. We need to find the
378 * Phi node in the merge block and delete it (while using the SSA name
379 * of the merge as the target of the SELECT. Delete both taken and
380 * fallthrough blocks, and set fallthrough to merge block.
381 * NOTE: not updating other dataflow info (no longer used at this point).
382 * If this changes, need to update i_dom, etc. here (and in CombineBlocks).
383 */
384 if (opcode == Instruction::IF_NEZ) {
385 // Normalize.
386 MIR* tmp_mir = if_true;
387 if_true = if_false;
388 if_false = tmp_mir;
389 }
390 mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpSelect);
391 bool const_form = (SelectKind(if_true) == kSelectConst);
392 if ((SelectKind(if_true) == kSelectMove)) {
393 if (IsConst(if_true->ssa_rep->uses[0]) &&
394 IsConst(if_false->ssa_rep->uses[0])) {
395 const_form = true;
396 if_true->dalvikInsn.vB = ConstantValue(if_true->ssa_rep->uses[0]);
397 if_false->dalvikInsn.vB = ConstantValue(if_false->ssa_rep->uses[0]);
398 }
399 }
400 if (const_form) {
401 // "true" set val in vB
402 mir->dalvikInsn.vB = if_true->dalvikInsn.vB;
403 // "false" set val in vC
404 mir->dalvikInsn.vC = if_false->dalvikInsn.vB;
405 } else {
406 DCHECK_EQ(SelectKind(if_true), kSelectMove);
407 DCHECK_EQ(SelectKind(if_false), kSelectMove);
408 int* src_ssa = static_cast<int*>(NewMem(cu_, sizeof(int) * 3, false,
409 kAllocDFInfo));
410 src_ssa[0] = mir->ssa_rep->uses[0];
411 src_ssa[1] = if_true->ssa_rep->uses[0];
412 src_ssa[2] = if_false->ssa_rep->uses[0];
413 mir->ssa_rep->uses = src_ssa;
414 mir->ssa_rep->num_uses = 3;
415 }
416 mir->ssa_rep->num_defs = 1;
417 mir->ssa_rep->defs = static_cast<int*>(NewMem(cu_, sizeof(int) * 1, false,
418 kAllocDFInfo));
419 mir->ssa_rep->fp_def = static_cast<bool*>(NewMem(cu_, sizeof(bool) * 1, false,
420 kAllocDFInfo));
421 mir->ssa_rep->fp_def[0] = if_true->ssa_rep->fp_def[0];
422 /*
423 * There is usually a Phi node in the join block for our two cases. If the
424 * Phi node only contains our two cases as input, we will use the result
425 * SSA name of the Phi node as our select result and delete the Phi. If
426 * the Phi node has more than two operands, we will arbitrarily use the SSA
427 * name of the "true" path, delete the SSA name of the "false" path from the
428 * Phi node (and fix up the incoming arc list).
429 */
430 if (phi->ssa_rep->num_uses == 2) {
431 mir->ssa_rep->defs[0] = phi->ssa_rep->defs[0];
432 phi->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
433 } else {
434 int dead_def = if_false->ssa_rep->defs[0];
435 int live_def = if_true->ssa_rep->defs[0];
436 mir->ssa_rep->defs[0] = live_def;
437 int* incoming = reinterpret_cast<int*>(phi->dalvikInsn.vB);
438 for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
439 if (phi->ssa_rep->uses[i] == live_def) {
440 incoming[i] = bb->id;
441 }
442 }
443 for (int i = 0; i < phi->ssa_rep->num_uses; i++) {
444 if (phi->ssa_rep->uses[i] == dead_def) {
445 int last_slot = phi->ssa_rep->num_uses - 1;
446 phi->ssa_rep->uses[i] = phi->ssa_rep->uses[last_slot];
447 incoming[i] = incoming[last_slot];
448 }
449 }
450 }
451 phi->ssa_rep->num_uses--;
452 bb->taken = NULL;
453 tk->block_type = kDead;
454 for (MIR* tmir = ft->first_mir_insn; tmir != NULL; tmir = tmir->next) {
455 tmir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
456 }
457 }
458 }
459 }
460 }
461 }
462 bb = NextDominatedBlock(bb);
463 }
464
465 if (num_temps > cu_->num_compiler_temps) {
466 cu_->num_compiler_temps = num_temps;
467 }
468 return true;
469}
470
471bool MIRGraph::NullCheckEliminationInit(struct BasicBlock* bb)
472{
473 if (bb->data_flow_info == NULL) return false;
474 bb->data_flow_info->ending_null_check_v =
475 AllocBitVector(cu_, GetNumSSARegs(), false, kBitMapNullCheck);
476 ClearAllBits(bb->data_flow_info->ending_null_check_v);
477 return true;
478}
479
480/* Collect stats on number of checks removed */
481bool MIRGraph::CountChecks(struct BasicBlock* bb)
482{
483 if (bb->data_flow_info == NULL) return false;
484 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
485 if (mir->ssa_rep == NULL) {
486 continue;
487 }
488 int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
489 if (df_attributes & DF_HAS_NULL_CHKS) {
490 //TODO: move checkstats to mir_graph
491 cu_->checkstats->null_checks++;
492 if (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) {
493 cu_->checkstats->null_checks_eliminated++;
494 }
495 }
496 if (df_attributes & DF_HAS_RANGE_CHKS) {
497 cu_->checkstats->range_checks++;
498 if (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) {
499 cu_->checkstats->range_checks_eliminated++;
500 }
501 }
502 }
503 return false;
504}
505
506/* Try to make common case the fallthrough path */
507static bool LayoutBlocks(struct BasicBlock* bb)
508{
509 // TODO: For now, just looking for direct throws. Consider generalizing for profile feedback
510 if (!bb->explicit_throw) {
511 return false;
512 }
513 BasicBlock* walker = bb;
514 while (true) {
515 // Check termination conditions
516 if ((walker->block_type == kEntryBlock) || (Predecessors(walker) != 1)) {
517 break;
518 }
519 BasicBlock* prev = GET_ELEM_N(walker->predecessors, BasicBlock*, 0);
520 if (prev->conditional_branch) {
521 if (prev->fall_through == walker) {
522 // Already done - return
523 break;
524 }
525 DCHECK_EQ(walker, prev->taken);
526 // Got one. Flip it and exit
527 Instruction::Code opcode = prev->last_mir_insn->dalvikInsn.opcode;
528 switch (opcode) {
529 case Instruction::IF_EQ: opcode = Instruction::IF_NE; break;
530 case Instruction::IF_NE: opcode = Instruction::IF_EQ; break;
531 case Instruction::IF_LT: opcode = Instruction::IF_GE; break;
532 case Instruction::IF_GE: opcode = Instruction::IF_LT; break;
533 case Instruction::IF_GT: opcode = Instruction::IF_LE; break;
534 case Instruction::IF_LE: opcode = Instruction::IF_GT; break;
535 case Instruction::IF_EQZ: opcode = Instruction::IF_NEZ; break;
536 case Instruction::IF_NEZ: opcode = Instruction::IF_EQZ; break;
537 case Instruction::IF_LTZ: opcode = Instruction::IF_GEZ; break;
538 case Instruction::IF_GEZ: opcode = Instruction::IF_LTZ; break;
539 case Instruction::IF_GTZ: opcode = Instruction::IF_LEZ; break;
540 case Instruction::IF_LEZ: opcode = Instruction::IF_GTZ; break;
541 default: LOG(FATAL) << "Unexpected opcode " << opcode;
542 }
543 prev->last_mir_insn->dalvikInsn.opcode = opcode;
544 BasicBlock* t_bb = prev->taken;
545 prev->taken = prev->fall_through;
546 prev->fall_through = t_bb;
547 break;
548 }
549 walker = prev;
550 }
551 return false;
552}
553
554/* Combine any basic blocks terminated by instructions that we now know can't throw */
555bool MIRGraph::CombineBlocks(struct BasicBlock* bb)
556{
557 // Loop here to allow combining a sequence of blocks
558 while (true) {
559 // Check termination conditions
560 if ((bb->first_mir_insn == NULL)
561 || (bb->data_flow_info == NULL)
562 || (bb->block_type == kExceptionHandling)
563 || (bb->block_type == kExitBlock)
564 || (bb->block_type == kDead)
565 || ((bb->taken == NULL) || (bb->taken->block_type != kExceptionHandling))
566 || (bb->successor_block_list.block_list_type != kNotUsed)
567 || (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) {
568 break;
569 }
570
571 // Test the kMirOpCheck instruction
572 MIR* mir = bb->last_mir_insn;
573 // Grab the attributes from the paired opcode
574 MIR* throw_insn = mir->meta.throw_insn;
575 int df_attributes = oat_data_flow_attributes[throw_insn->dalvikInsn.opcode];
576 bool can_combine = true;
577 if (df_attributes & DF_HAS_NULL_CHKS) {
578 can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0);
579 }
580 if (df_attributes & DF_HAS_RANGE_CHKS) {
581 can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
582 }
583 if (!can_combine) {
584 break;
585 }
586 // OK - got one. Combine
587 BasicBlock* bb_next = bb->fall_through;
588 DCHECK(!bb_next->catch_entry);
589 DCHECK_EQ(Predecessors(bb_next), 1U);
590 MIR* t_mir = bb->last_mir_insn->prev;
591 // Overwrite the kOpCheck insn with the paired opcode
592 DCHECK_EQ(bb_next->first_mir_insn, throw_insn);
593 *bb->last_mir_insn = *throw_insn;
594 bb->last_mir_insn->prev = t_mir;
595 // Use the successor info from the next block
596 bb->successor_block_list = bb_next->successor_block_list;
597 // Use the ending block linkage from the next block
598 bb->fall_through = bb_next->fall_through;
599 bb->taken->block_type = kDead; // Kill the unused exception block
600 bb->taken = bb_next->taken;
601 // Include the rest of the instructions
602 bb->last_mir_insn = bb_next->last_mir_insn;
603 /*
604 * If lower-half of pair of blocks to combine contained a return, move the flag
605 * to the newly combined block.
606 */
607 bb->terminated_by_return = bb_next->terminated_by_return;
608
609 /*
610 * NOTE: we aren't updating all dataflow info here. Should either make sure this pass
611 * happens after uses of i_dominated, dom_frontier or update the dataflow info here.
612 */
613
614 // Kill bb_next and remap now-dead id to parent
615 bb_next->block_type = kDead;
616 cu_->block_id_map.Overwrite(bb_next->id, bb->id);
617
618 // Now, loop back and see if we can keep going
619 }
620 return false;
621}
622
623/* Eliminate unnecessary null checks for a basic block. */
624bool MIRGraph::EliminateNullChecks(struct BasicBlock* bb)
625{
626 if (bb->data_flow_info == NULL) return false;
627
628 /*
629 * Set initial state. Be conservative with catch
630 * blocks and start with no assumptions about null check
631 * status (except for "this").
632 */
633 if ((bb->block_type == kEntryBlock) | bb->catch_entry) {
634 ClearAllBits(temp_ssa_register_v_);
635 if ((cu_->access_flags & kAccStatic) == 0) {
636 // If non-static method, mark "this" as non-null
637 int this_reg = cu_->num_dalvik_registers - cu_->num_ins;
638 SetBit(cu_, temp_ssa_register_v_, this_reg);
639 }
640 } else {
641 // Starting state is intesection of all incoming arcs
642 GrowableListIterator iter;
643 GrowableListIteratorInit(bb->predecessors, &iter);
644 BasicBlock* pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter));
645 DCHECK(pred_bb != NULL);
646 CopyBitVector(temp_ssa_register_v_, pred_bb->data_flow_info->ending_null_check_v);
647 while (true) {
648 pred_bb = reinterpret_cast<BasicBlock*>(GrowableListIteratorNext(&iter));
649 if (!pred_bb) break;
650 if ((pred_bb->data_flow_info == NULL) ||
651 (pred_bb->data_flow_info->ending_null_check_v == NULL)) {
652 continue;
653 }
654 IntersectBitVectors(temp_ssa_register_v_, temp_ssa_register_v_,
655 pred_bb->data_flow_info->ending_null_check_v);
656 }
657 }
658
659 // Walk through the instruction in the block, updating as necessary
660 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
661 if (mir->ssa_rep == NULL) {
662 continue;
663 }
664 int df_attributes = oat_data_flow_attributes[mir->dalvikInsn.opcode];
665
666 // Mark target of NEW* as non-null
667 if (df_attributes & DF_NON_NULL_DST) {
668 SetBit(cu_, temp_ssa_register_v_, mir->ssa_rep->defs[0]);
669 }
670
671 // Mark non-null returns from invoke-style NEW*
672 if (df_attributes & DF_NON_NULL_RET) {
673 MIR* next_mir = mir->next;
674 // Next should be an MOVE_RESULT_OBJECT
675 if (next_mir &&
676 next_mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
677 // Mark as null checked
678 SetBit(cu_, temp_ssa_register_v_, next_mir->ssa_rep->defs[0]);
679 } else {
680 if (next_mir) {
681 LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
682 } else if (bb->fall_through) {
683 // Look in next basic block
684 struct BasicBlock* next_bb = bb->fall_through;
685 for (MIR* tmir = next_bb->first_mir_insn; tmir != NULL;
686 tmir =tmir->next) {
687 if (static_cast<int>(tmir->dalvikInsn.opcode) >= static_cast<int>(kMirOpFirst)) {
688 continue;
689 }
690 // First non-pseudo should be MOVE_RESULT_OBJECT
691 if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
692 // Mark as null checked
693 SetBit(cu_, temp_ssa_register_v_, tmir->ssa_rep->defs[0]);
694 } else {
695 LOG(WARNING) << "Unexpected op after new: " << tmir->dalvikInsn.opcode;
696 }
697 break;
698 }
699 }
700 }
701 }
702
703 /*
704 * Propagate nullcheck state on register copies (including
705 * Phi pseudo copies. For the latter, nullcheck state is
706 * the "and" of all the Phi's operands.
707 */
708 if (df_attributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) {
709 int tgt_sreg = mir->ssa_rep->defs[0];
710 int operands = (df_attributes & DF_NULL_TRANSFER_0) ? 1 :
711 mir->ssa_rep->num_uses;
712 bool null_checked = true;
713 for (int i = 0; i < operands; i++) {
714 null_checked &= IsBitSet(temp_ssa_register_v_,
715 mir->ssa_rep->uses[i]);
716 }
717 if (null_checked) {
718 SetBit(cu_, temp_ssa_register_v_, tgt_sreg);
719 }
720 }
721
722 // Already nullchecked?
723 if ((df_attributes & DF_HAS_NULL_CHKS) && !(mir->optimization_flags & MIR_IGNORE_NULL_CHECK)) {
724 int src_idx;
725 if (df_attributes & DF_NULL_CHK_1) {
726 src_idx = 1;
727 } else if (df_attributes & DF_NULL_CHK_2) {
728 src_idx = 2;
729 } else {
730 src_idx = 0;
731 }
732 int src_sreg = mir->ssa_rep->uses[src_idx];
733 if (IsBitSet(temp_ssa_register_v_, src_sreg)) {
734 // Eliminate the null check
735 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
736 } else {
737 // Mark s_reg as null-checked
738 SetBit(cu_, temp_ssa_register_v_, src_sreg);
739 }
740 }
741 }
742
743 // Did anything change?
744 bool res = CompareBitVectors(bb->data_flow_info->ending_null_check_v,
745 temp_ssa_register_v_);
746 if (res) {
747 CopyBitVector(bb->data_flow_info->ending_null_check_v,
748 temp_ssa_register_v_);
749 }
750 return res;
751}
752
753void MIRGraph::NullCheckElimination()
754{
755 if (!(cu_->disable_opt & (1 << kNullCheckElimination))) {
756 DCHECK(temp_ssa_register_v_ != NULL);
buzbee0665fe02013-03-21 12:32:21 -0700757 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800758 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
759 NullCheckEliminationInit(bb);
760 }
buzbee0665fe02013-03-21 12:32:21 -0700761 PreOrderDfsIterator iter2(this, true /* iterative */);
buzbee311ca162013-02-28 15:56:43 -0800762 bool change = false;
763 for (BasicBlock* bb = iter2.Next(change); bb != NULL; bb = iter2.Next(change)) {
764 change = EliminateNullChecks(bb);
765 }
766 }
767 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
768 DumpCFG("/sdcard/4_post_nce_cfg/", false);
769 }
770}
771
772void MIRGraph::BasicBlockCombine()
773{
buzbee0665fe02013-03-21 12:32:21 -0700774 PreOrderDfsIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800775 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
776 CombineBlocks(bb);
777 }
778 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
779 DumpCFG("/sdcard/5_post_bbcombine_cfg/", false);
780 }
781}
782
783void MIRGraph::CodeLayout()
784{
buzbee0665fe02013-03-21 12:32:21 -0700785 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800786 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
787 LayoutBlocks(bb);
788 }
789 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
790 DumpCFG("/sdcard/2_post_layout_cfg/", true);
791 }
792}
793
794void MIRGraph::DumpCheckStats()
795{
796 Checkstats* stats =
797 static_cast<Checkstats*>(NewMem(cu_, sizeof(Checkstats), true, kAllocDFInfo));
798 cu_->checkstats = stats;
buzbee0665fe02013-03-21 12:32:21 -0700799 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800800 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
801 CountChecks(bb);
802 }
803 if (stats->null_checks > 0) {
804 float eliminated = static_cast<float>(stats->null_checks_eliminated);
805 float checks = static_cast<float>(stats->null_checks);
806 LOG(INFO) << "Null Checks: " << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
807 << stats->null_checks_eliminated << " of " << stats->null_checks << " -> "
808 << (eliminated/checks) * 100.0 << "%";
809 }
810 if (stats->range_checks > 0) {
811 float eliminated = static_cast<float>(stats->range_checks_eliminated);
812 float checks = static_cast<float>(stats->range_checks);
813 LOG(INFO) << "Range Checks: " << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
814 << stats->range_checks_eliminated << " of " << stats->range_checks << " -> "
815 << (eliminated/checks) * 100.0 << "%";
816 }
817}
818
819bool MIRGraph::BuildExtendedBBList(struct BasicBlock* bb)
820{
821 if (bb->visited) return false;
822 if (!((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
823 || (bb->block_type == kExitBlock))) {
824 // Ignore special blocks
825 bb->visited = true;
826 return false;
827 }
828 // Must be head of extended basic block.
829 BasicBlock* start_bb = bb;
830 extended_basic_blocks_.push_back(bb);
831 bool terminated_by_return = false;
832 // Visit blocks strictly dominated by this head.
833 while (bb != NULL) {
834 bb->visited = true;
835 terminated_by_return |= bb->terminated_by_return;
836 bb = NextDominatedBlock(bb);
837 }
838 if (terminated_by_return) {
839 // This extended basic block contains a return, so mark all members.
840 bb = start_bb;
841 while (bb != NULL) {
842 bb->dominates_return = true;
843 bb = NextDominatedBlock(bb);
844 }
845 }
846 return false; // Not iterative - return value will be ignored
847}
848
849
850void MIRGraph::BasicBlockOptimization()
851{
852 if (!(cu_->disable_opt & (1 << kBBOpt))) {
853 CompilerInitGrowableList(cu_, &cu_->compiler_temps, 6, kListMisc);
854 DCHECK_EQ(cu_->num_compiler_temps, 0);
855 // Mark all blocks as not visited
buzbee0665fe02013-03-21 12:32:21 -0700856 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800857 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
858 ClearVisitedFlag(bb);
859 }
buzbee0665fe02013-03-21 12:32:21 -0700860 PreOrderDfsIterator iter2(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800861 for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
862 BuildExtendedBBList(bb);
863 }
864 // Perform extended basic block optimizations.
865 for (unsigned int i = 0; i < extended_basic_blocks_.size(); i++) {
866 BasicBlockOpt(extended_basic_blocks_[i]);
867 }
868 }
869 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
870 DumpCFG("/sdcard/6_post_bbo_cfg/", false);
871 }
872}
873
874} // namespace art