blob: 54a9a83a1f6243e73a136d0f620cfafbc12f2395 [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{
buzbee862a7602013-04-05 10:58:54 -070025 return bb->predecessors->Size();
buzbee311ca162013-02-28 15:56:43 -080026}
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{
buzbee862a7602013-04-05 10:58:54 -070031 is_constant_v_->SetBit(ssa_reg);
buzbee311ca162013-02-28 15:56:43 -080032 constant_values_[ssa_reg] = value;
33}
34
35void MIRGraph::SetConstantWide(int ssa_reg, int64_t value)
36{
buzbee862a7602013-04-05 10:58:54 -070037 is_constant_v_->SetBit(ssa_reg);
buzbee311ca162013-02-28 15:56:43 -080038 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;
buzbee311ca162013-02-28 15:56:43 -080045
46 for (mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
buzbee1fd33462013-03-25 13:40:45 -070047 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
buzbee311ca162013-02-28 15:56:43 -080048
49 DecodedInstruction *d_insn = &mir->dalvikInsn;
50
51 if (!(df_attributes & DF_HAS_DEFS)) continue;
52
53 /* Handle instructions that set up constants directly */
54 if (df_attributes & DF_SETS_CONST) {
55 if (df_attributes & DF_DA) {
56 int32_t vB = static_cast<int32_t>(d_insn->vB);
57 switch (d_insn->opcode) {
58 case Instruction::CONST_4:
59 case Instruction::CONST_16:
60 case Instruction::CONST:
61 SetConstant(mir->ssa_rep->defs[0], vB);
62 break;
63 case Instruction::CONST_HIGH16:
64 SetConstant(mir->ssa_rep->defs[0], vB << 16);
65 break;
66 case Instruction::CONST_WIDE_16:
67 case Instruction::CONST_WIDE_32:
68 SetConstantWide(mir->ssa_rep->defs[0], static_cast<int64_t>(vB));
69 break;
70 case Instruction::CONST_WIDE:
71 SetConstantWide(mir->ssa_rep->defs[0],d_insn->vB_wide);
72 break;
73 case Instruction::CONST_WIDE_HIGH16:
74 SetConstantWide(mir->ssa_rep->defs[0], static_cast<int64_t>(vB) << 48);
75 break;
76 default:
77 break;
78 }
79 }
80 /* Handle instructions that set up constants directly */
81 } else if (df_attributes & DF_IS_MOVE) {
82 int i;
83
84 for (i = 0; i < mir->ssa_rep->num_uses; i++) {
buzbee862a7602013-04-05 10:58:54 -070085 if (!is_constant_v_->IsBitSet(mir->ssa_rep->uses[i])) break;
buzbee311ca162013-02-28 15:56:43 -080086 }
87 /* Move a register holding a constant to another register */
88 if (i == mir->ssa_rep->num_uses) {
89 SetConstant(mir->ssa_rep->defs[0], constant_values_[mir->ssa_rep->uses[0]]);
90 if (df_attributes & DF_A_WIDE) {
91 SetConstant(mir->ssa_rep->defs[1], constant_values_[mir->ssa_rep->uses[1]]);
92 }
93 }
94 }
95 }
96 /* TODO: implement code to handle arithmetic operations */
97 return true;
98}
99
100void MIRGraph::PropagateConstants()
101{
buzbee862a7602013-04-05 10:58:54 -0700102 is_constant_v_ = new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false);
103 constant_values_ = static_cast<int*>(arena_->NewMem(sizeof(int) * GetNumSSARegs(), true,
104 ArenaAllocator::kAllocDFInfo));
buzbee0665fe02013-03-21 12:32:21 -0700105 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800106 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
107 DoConstantPropogation(bb);
108 }
buzbee311ca162013-02-28 15:56:43 -0800109}
110
111/* Advance to next strictly dominated MIR node in an extended basic block */
112static MIR* AdvanceMIR(BasicBlock** p_bb, MIR* mir)
113{
114 BasicBlock* bb = *p_bb;
115 if (mir != NULL) {
116 mir = mir->next;
117 if (mir == NULL) {
118 bb = bb->fall_through;
119 if ((bb == NULL) || Predecessors(bb) != 1) {
120 mir = NULL;
121 } else {
122 *p_bb = bb;
123 mir = bb->first_mir_insn;
124 }
125 }
126 }
127 return mir;
128}
129
130/*
131 * To be used at an invoke mir. If the logically next mir node represents
132 * a move-result, return it. Else, return NULL. If a move-result exists,
133 * it is required to immediately follow the invoke with no intervening
134 * opcodes or incoming arcs. However, if the result of the invoke is not
135 * used, a move-result may not be present.
136 */
137MIR* MIRGraph::FindMoveResult(BasicBlock* bb, MIR* mir)
138{
139 BasicBlock* tbb = bb;
140 mir = AdvanceMIR(&tbb, mir);
141 while (mir != NULL) {
142 int opcode = mir->dalvikInsn.opcode;
143 if ((mir->dalvikInsn.opcode == Instruction::MOVE_RESULT) ||
144 (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) ||
145 (mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_WIDE)) {
146 break;
147 }
148 // Keep going if pseudo op, otherwise terminate
149 if (opcode < kNumPackedOpcodes) {
150 mir = NULL;
151 } else {
152 mir = AdvanceMIR(&tbb, mir);
153 }
154 }
155 return mir;
156}
157
158static BasicBlock* NextDominatedBlock(BasicBlock* bb)
159{
160 if (bb->block_type == kDead) {
161 return NULL;
162 }
163 DCHECK((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
164 || (bb->block_type == kExitBlock));
165 bb = bb->fall_through;
166 if (bb == NULL || (Predecessors(bb) != 1)) {
167 return NULL;
168 }
169 DCHECK((bb->block_type == kDalvikByteCode) || (bb->block_type == kExitBlock));
170 return bb;
171}
172
173static MIR* FindPhi(BasicBlock* bb, int ssa_name)
174{
175 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
176 if (static_cast<int>(mir->dalvikInsn.opcode) == kMirOpPhi) {
177 for (int i = 0; i < mir->ssa_rep->num_uses; i++) {
178 if (mir->ssa_rep->uses[i] == ssa_name) {
179 return mir;
180 }
181 }
182 }
183 }
184 return NULL;
185}
186
187static SelectInstructionKind SelectKind(MIR* mir)
188{
189 switch (mir->dalvikInsn.opcode) {
190 case Instruction::MOVE:
191 case Instruction::MOVE_OBJECT:
192 case Instruction::MOVE_16:
193 case Instruction::MOVE_OBJECT_16:
194 case Instruction::MOVE_FROM16:
195 case Instruction::MOVE_OBJECT_FROM16:
196 return kSelectMove;
197 case Instruction::CONST:
198 case Instruction::CONST_4:
199 case Instruction::CONST_16:
200 return kSelectConst;
201 case Instruction::GOTO:
202 case Instruction::GOTO_16:
203 case Instruction::GOTO_32:
204 return kSelectGoto;
205 default:;
206 }
207 return kSelectNone;
208}
209
210int MIRGraph::GetSSAUseCount(int s_reg)
211{
buzbee862a7602013-04-05 10:58:54 -0700212 return raw_use_counts_.Get(s_reg);
buzbee311ca162013-02-28 15:56:43 -0800213}
214
215
216/* Do some MIR-level extended basic block optimizations */
217bool MIRGraph::BasicBlockOpt(BasicBlock* bb)
218{
219 if (bb->block_type == kDead) {
220 return true;
221 }
222 int num_temps = 0;
223 LocalValueNumbering local_valnum(cu_);
224 while (bb != NULL) {
225 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
226 // TUNING: use the returned value number for CSE.
227 local_valnum.GetValueNumber(mir);
228 // Look for interesting opcodes, skip otherwise
229 Instruction::Code opcode = mir->dalvikInsn.opcode;
230 switch (opcode) {
231 case Instruction::CMPL_FLOAT:
232 case Instruction::CMPL_DOUBLE:
233 case Instruction::CMPG_FLOAT:
234 case Instruction::CMPG_DOUBLE:
235 case Instruction::CMP_LONG:
buzbee1fd33462013-03-25 13:40:45 -0700236 if ((cu_->disable_opt & (1 << kBranchFusing)) != 0) {
buzbee311ca162013-02-28 15:56:43 -0800237 // Bitcode doesn't allow this optimization.
238 break;
239 }
240 if (mir->next != NULL) {
241 MIR* mir_next = mir->next;
242 Instruction::Code br_opcode = mir_next->dalvikInsn.opcode;
243 ConditionCode ccode = kCondNv;
244 switch(br_opcode) {
245 case Instruction::IF_EQZ:
246 ccode = kCondEq;
247 break;
248 case Instruction::IF_NEZ:
249 ccode = kCondNe;
250 break;
251 case Instruction::IF_LTZ:
252 ccode = kCondLt;
253 break;
254 case Instruction::IF_GEZ:
255 ccode = kCondGe;
256 break;
257 case Instruction::IF_GTZ:
258 ccode = kCondGt;
259 break;
260 case Instruction::IF_LEZ:
261 ccode = kCondLe;
262 break;
263 default:
264 break;
265 }
266 // Make sure result of cmp is used by next insn and nowhere else
267 if ((ccode != kCondNv) &&
268 (mir->ssa_rep->defs[0] == mir_next->ssa_rep->uses[0]) &&
269 (GetSSAUseCount(mir->ssa_rep->defs[0]) == 1)) {
270 mir_next->dalvikInsn.arg[0] = ccode;
271 switch(opcode) {
272 case Instruction::CMPL_FLOAT:
273 mir_next->dalvikInsn.opcode =
274 static_cast<Instruction::Code>(kMirOpFusedCmplFloat);
275 break;
276 case Instruction::CMPL_DOUBLE:
277 mir_next->dalvikInsn.opcode =
278 static_cast<Instruction::Code>(kMirOpFusedCmplDouble);
279 break;
280 case Instruction::CMPG_FLOAT:
281 mir_next->dalvikInsn.opcode =
282 static_cast<Instruction::Code>(kMirOpFusedCmpgFloat);
283 break;
284 case Instruction::CMPG_DOUBLE:
285 mir_next->dalvikInsn.opcode =
286 static_cast<Instruction::Code>(kMirOpFusedCmpgDouble);
287 break;
288 case Instruction::CMP_LONG:
289 mir_next->dalvikInsn.opcode =
290 static_cast<Instruction::Code>(kMirOpFusedCmpLong);
291 break;
292 default: LOG(ERROR) << "Unexpected opcode: " << opcode;
293 }
294 mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpNop);
295 mir_next->ssa_rep->num_uses = mir->ssa_rep->num_uses;
296 mir_next->ssa_rep->uses = mir->ssa_rep->uses;
297 mir_next->ssa_rep->fp_use = mir->ssa_rep->fp_use;
298 mir_next->ssa_rep->num_defs = 0;
299 mir->ssa_rep->num_uses = 0;
300 mir->ssa_rep->num_defs = 0;
301 }
302 }
303 break;
304 case Instruction::GOTO:
305 case Instruction::GOTO_16:
306 case Instruction::GOTO_32:
307 case Instruction::IF_EQ:
308 case Instruction::IF_NE:
309 case Instruction::IF_LT:
310 case Instruction::IF_GE:
311 case Instruction::IF_GT:
312 case Instruction::IF_LE:
313 case Instruction::IF_EQZ:
314 case Instruction::IF_NEZ:
315 case Instruction::IF_LTZ:
316 case Instruction::IF_GEZ:
317 case Instruction::IF_GTZ:
318 case Instruction::IF_LEZ:
319 if (bb->taken->dominates_return) {
320 mir->optimization_flags |= MIR_IGNORE_SUSPEND_CHECK;
321 if (cu_->verbose) {
322 LOG(INFO) << "Suppressed suspend check on branch to return at 0x" << std::hex << mir->offset;
323 }
324 }
325 break;
326 default:
327 break;
328 }
329 // Is this the select pattern?
330 // TODO: flesh out support for Mips and X86. NOTE: llvm's select op doesn't quite work here.
331 // TUNING: expand to support IF_xx compare & branches
buzbee1fd33462013-03-25 13:40:45 -0700332 if (!(cu_->compiler_backend == kPortable) && (cu_->instruction_set == kThumb2) &&
buzbee311ca162013-02-28 15:56:43 -0800333 ((mir->dalvikInsn.opcode == Instruction::IF_EQZ) ||
334 (mir->dalvikInsn.opcode == Instruction::IF_NEZ))) {
335 BasicBlock* ft = bb->fall_through;
336 DCHECK(ft != NULL);
337 BasicBlock* ft_ft = ft->fall_through;
338 BasicBlock* ft_tk = ft->taken;
339
340 BasicBlock* tk = bb->taken;
341 DCHECK(tk != NULL);
342 BasicBlock* tk_ft = tk->fall_through;
343 BasicBlock* tk_tk = tk->taken;
344
345 /*
346 * In the select pattern, the taken edge goes to a block that unconditionally
347 * transfers to the rejoin block and the fall_though edge goes to a block that
348 * unconditionally falls through to the rejoin block.
349 */
350 if ((tk_ft == NULL) && (ft_tk == NULL) && (tk_tk == ft_ft) &&
351 (Predecessors(tk) == 1) && (Predecessors(ft) == 1)) {
352 /*
353 * Okay - we have the basic diamond shape. At the very least, we can eliminate the
354 * suspend check on the taken-taken branch back to the join point.
355 */
356 if (SelectKind(tk->last_mir_insn) == kSelectGoto) {
357 tk->last_mir_insn->optimization_flags |= (MIR_IGNORE_SUSPEND_CHECK);
358 }
359 // Are the block bodies something we can handle?
360 if ((ft->first_mir_insn == ft->last_mir_insn) &&
361 (tk->first_mir_insn != tk->last_mir_insn) &&
362 (tk->first_mir_insn->next == tk->last_mir_insn) &&
363 ((SelectKind(ft->first_mir_insn) == kSelectMove) ||
364 (SelectKind(ft->first_mir_insn) == kSelectConst)) &&
365 (SelectKind(ft->first_mir_insn) == SelectKind(tk->first_mir_insn)) &&
366 (SelectKind(tk->last_mir_insn) == kSelectGoto)) {
367 // Almost there. Are the instructions targeting the same vreg?
368 MIR* if_true = tk->first_mir_insn;
369 MIR* if_false = ft->first_mir_insn;
370 // It's possible that the target of the select isn't used - skip those (rare) cases.
371 MIR* phi = FindPhi(tk_tk, if_true->ssa_rep->defs[0]);
372 if ((phi != NULL) && (if_true->dalvikInsn.vA == if_false->dalvikInsn.vA)) {
373 /*
374 * We'll convert the IF_EQZ/IF_NEZ to a SELECT. We need to find the
375 * Phi node in the merge block and delete it (while using the SSA name
376 * of the merge as the target of the SELECT. Delete both taken and
377 * fallthrough blocks, and set fallthrough to merge block.
378 * NOTE: not updating other dataflow info (no longer used at this point).
379 * If this changes, need to update i_dom, etc. here (and in CombineBlocks).
380 */
381 if (opcode == Instruction::IF_NEZ) {
382 // Normalize.
383 MIR* tmp_mir = if_true;
384 if_true = if_false;
385 if_false = tmp_mir;
386 }
387 mir->dalvikInsn.opcode = static_cast<Instruction::Code>(kMirOpSelect);
388 bool const_form = (SelectKind(if_true) == kSelectConst);
389 if ((SelectKind(if_true) == kSelectMove)) {
390 if (IsConst(if_true->ssa_rep->uses[0]) &&
391 IsConst(if_false->ssa_rep->uses[0])) {
392 const_form = true;
393 if_true->dalvikInsn.vB = ConstantValue(if_true->ssa_rep->uses[0]);
394 if_false->dalvikInsn.vB = ConstantValue(if_false->ssa_rep->uses[0]);
395 }
396 }
397 if (const_form) {
398 // "true" set val in vB
399 mir->dalvikInsn.vB = if_true->dalvikInsn.vB;
400 // "false" set val in vC
401 mir->dalvikInsn.vC = if_false->dalvikInsn.vB;
402 } else {
403 DCHECK_EQ(SelectKind(if_true), kSelectMove);
404 DCHECK_EQ(SelectKind(if_false), kSelectMove);
buzbee862a7602013-04-05 10:58:54 -0700405 int* src_ssa =
406 static_cast<int*>(arena_->NewMem(sizeof(int) * 3, false,
407 ArenaAllocator::kAllocDFInfo));
buzbee311ca162013-02-28 15:56:43 -0800408 src_ssa[0] = mir->ssa_rep->uses[0];
409 src_ssa[1] = if_true->ssa_rep->uses[0];
410 src_ssa[2] = if_false->ssa_rep->uses[0];
411 mir->ssa_rep->uses = src_ssa;
412 mir->ssa_rep->num_uses = 3;
413 }
414 mir->ssa_rep->num_defs = 1;
buzbee862a7602013-04-05 10:58:54 -0700415 mir->ssa_rep->defs =
416 static_cast<int*>(arena_->NewMem(sizeof(int) * 1, false,
417 ArenaAllocator::kAllocDFInfo));
418 mir->ssa_rep->fp_def =
419 static_cast<bool*>(arena_->NewMem(sizeof(bool) * 1, false,
420 ArenaAllocator::kAllocDFInfo));
buzbee311ca162013-02-28 15:56:43 -0800421 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
buzbee862a7602013-04-05 10:58:54 -0700471void MIRGraph::NullCheckEliminationInit(struct BasicBlock* bb)
buzbee311ca162013-02-28 15:56:43 -0800472{
buzbee862a7602013-04-05 10:58:54 -0700473 if (bb->data_flow_info != NULL) {
474 bb->data_flow_info->ending_null_check_v =
475 new (arena_) ArenaBitVector(arena_, GetNumSSARegs(), false, kBitMapNullCheck);
476 }
buzbee311ca162013-02-28 15:56:43 -0800477}
478
479/* Collect stats on number of checks removed */
buzbee862a7602013-04-05 10:58:54 -0700480void MIRGraph::CountChecks(struct BasicBlock* bb)
buzbee311ca162013-02-28 15:56:43 -0800481{
buzbee862a7602013-04-05 10:58:54 -0700482 if (bb->data_flow_info != NULL) {
483 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
484 if (mir->ssa_rep == NULL) {
485 continue;
buzbee311ca162013-02-28 15:56:43 -0800486 }
buzbee862a7602013-04-05 10:58:54 -0700487 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
488 if (df_attributes & DF_HAS_NULL_CHKS) {
489 checkstats_->null_checks++;
490 if (mir->optimization_flags & MIR_IGNORE_NULL_CHECK) {
491 checkstats_->null_checks_eliminated++;
492 }
493 }
494 if (df_attributes & DF_HAS_RANGE_CHKS) {
495 checkstats_->range_checks++;
496 if (mir->optimization_flags & MIR_IGNORE_RANGE_CHECK) {
497 checkstats_->range_checks_eliminated++;
498 }
buzbee311ca162013-02-28 15:56:43 -0800499 }
500 }
501 }
buzbee311ca162013-02-28 15:56:43 -0800502}
503
504/* Try to make common case the fallthrough path */
505static bool LayoutBlocks(struct BasicBlock* bb)
506{
507 // TODO: For now, just looking for direct throws. Consider generalizing for profile feedback
508 if (!bb->explicit_throw) {
509 return false;
510 }
511 BasicBlock* walker = bb;
512 while (true) {
513 // Check termination conditions
514 if ((walker->block_type == kEntryBlock) || (Predecessors(walker) != 1)) {
515 break;
516 }
buzbee862a7602013-04-05 10:58:54 -0700517 BasicBlock* prev = walker->predecessors->Get(0);
buzbee311ca162013-02-28 15:56:43 -0800518 if (prev->conditional_branch) {
519 if (prev->fall_through == walker) {
520 // Already done - return
521 break;
522 }
523 DCHECK_EQ(walker, prev->taken);
524 // Got one. Flip it and exit
525 Instruction::Code opcode = prev->last_mir_insn->dalvikInsn.opcode;
526 switch (opcode) {
527 case Instruction::IF_EQ: opcode = Instruction::IF_NE; break;
528 case Instruction::IF_NE: opcode = Instruction::IF_EQ; break;
529 case Instruction::IF_LT: opcode = Instruction::IF_GE; break;
530 case Instruction::IF_GE: opcode = Instruction::IF_LT; break;
531 case Instruction::IF_GT: opcode = Instruction::IF_LE; break;
532 case Instruction::IF_LE: opcode = Instruction::IF_GT; break;
533 case Instruction::IF_EQZ: opcode = Instruction::IF_NEZ; break;
534 case Instruction::IF_NEZ: opcode = Instruction::IF_EQZ; break;
535 case Instruction::IF_LTZ: opcode = Instruction::IF_GEZ; break;
536 case Instruction::IF_GEZ: opcode = Instruction::IF_LTZ; break;
537 case Instruction::IF_GTZ: opcode = Instruction::IF_LEZ; break;
538 case Instruction::IF_LEZ: opcode = Instruction::IF_GTZ; break;
539 default: LOG(FATAL) << "Unexpected opcode " << opcode;
540 }
541 prev->last_mir_insn->dalvikInsn.opcode = opcode;
542 BasicBlock* t_bb = prev->taken;
543 prev->taken = prev->fall_through;
544 prev->fall_through = t_bb;
545 break;
546 }
547 walker = prev;
548 }
549 return false;
550}
551
552/* Combine any basic blocks terminated by instructions that we now know can't throw */
553bool MIRGraph::CombineBlocks(struct BasicBlock* bb)
554{
555 // Loop here to allow combining a sequence of blocks
556 while (true) {
557 // Check termination conditions
558 if ((bb->first_mir_insn == NULL)
559 || (bb->data_flow_info == NULL)
560 || (bb->block_type == kExceptionHandling)
561 || (bb->block_type == kExitBlock)
562 || (bb->block_type == kDead)
563 || ((bb->taken == NULL) || (bb->taken->block_type != kExceptionHandling))
564 || (bb->successor_block_list.block_list_type != kNotUsed)
565 || (static_cast<int>(bb->last_mir_insn->dalvikInsn.opcode) != kMirOpCheck)) {
566 break;
567 }
568
569 // Test the kMirOpCheck instruction
570 MIR* mir = bb->last_mir_insn;
571 // Grab the attributes from the paired opcode
572 MIR* throw_insn = mir->meta.throw_insn;
buzbee1fd33462013-03-25 13:40:45 -0700573 int df_attributes = oat_data_flow_attributes_[throw_insn->dalvikInsn.opcode];
buzbee311ca162013-02-28 15:56:43 -0800574 bool can_combine = true;
575 if (df_attributes & DF_HAS_NULL_CHKS) {
576 can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_NULL_CHECK) != 0);
577 }
578 if (df_attributes & DF_HAS_RANGE_CHKS) {
579 can_combine &= ((throw_insn->optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0);
580 }
581 if (!can_combine) {
582 break;
583 }
584 // OK - got one. Combine
585 BasicBlock* bb_next = bb->fall_through;
586 DCHECK(!bb_next->catch_entry);
587 DCHECK_EQ(Predecessors(bb_next), 1U);
588 MIR* t_mir = bb->last_mir_insn->prev;
589 // Overwrite the kOpCheck insn with the paired opcode
590 DCHECK_EQ(bb_next->first_mir_insn, throw_insn);
591 *bb->last_mir_insn = *throw_insn;
592 bb->last_mir_insn->prev = t_mir;
593 // Use the successor info from the next block
594 bb->successor_block_list = bb_next->successor_block_list;
595 // Use the ending block linkage from the next block
596 bb->fall_through = bb_next->fall_through;
597 bb->taken->block_type = kDead; // Kill the unused exception block
598 bb->taken = bb_next->taken;
599 // Include the rest of the instructions
600 bb->last_mir_insn = bb_next->last_mir_insn;
601 /*
602 * If lower-half of pair of blocks to combine contained a return, move the flag
603 * to the newly combined block.
604 */
605 bb->terminated_by_return = bb_next->terminated_by_return;
606
607 /*
608 * NOTE: we aren't updating all dataflow info here. Should either make sure this pass
609 * happens after uses of i_dominated, dom_frontier or update the dataflow info here.
610 */
611
612 // Kill bb_next and remap now-dead id to parent
613 bb_next->block_type = kDead;
buzbee1fd33462013-03-25 13:40:45 -0700614 block_id_map_.Overwrite(bb_next->id, bb->id);
buzbee311ca162013-02-28 15:56:43 -0800615
616 // Now, loop back and see if we can keep going
617 }
618 return false;
619}
620
621/* Eliminate unnecessary null checks for a basic block. */
622bool MIRGraph::EliminateNullChecks(struct BasicBlock* bb)
623{
624 if (bb->data_flow_info == NULL) return false;
625
626 /*
627 * Set initial state. Be conservative with catch
628 * blocks and start with no assumptions about null check
629 * status (except for "this").
630 */
631 if ((bb->block_type == kEntryBlock) | bb->catch_entry) {
buzbee862a7602013-04-05 10:58:54 -0700632 temp_ssa_register_v_->ClearAllBits();
buzbee311ca162013-02-28 15:56:43 -0800633 if ((cu_->access_flags & kAccStatic) == 0) {
634 // If non-static method, mark "this" as non-null
635 int this_reg = cu_->num_dalvik_registers - cu_->num_ins;
buzbee862a7602013-04-05 10:58:54 -0700636 temp_ssa_register_v_->SetBit(this_reg);
buzbee311ca162013-02-28 15:56:43 -0800637 }
638 } else {
639 // Starting state is intesection of all incoming arcs
buzbee862a7602013-04-05 10:58:54 -0700640 GrowableArray<BasicBlock*>::Iterator iter(bb->predecessors);
641 BasicBlock* pred_bb = iter.Next();
buzbee311ca162013-02-28 15:56:43 -0800642 DCHECK(pred_bb != NULL);
buzbee862a7602013-04-05 10:58:54 -0700643 temp_ssa_register_v_->Copy(pred_bb->data_flow_info->ending_null_check_v);
buzbee311ca162013-02-28 15:56:43 -0800644 while (true) {
buzbee862a7602013-04-05 10:58:54 -0700645 pred_bb = iter.Next();
buzbee311ca162013-02-28 15:56:43 -0800646 if (!pred_bb) break;
647 if ((pred_bb->data_flow_info == NULL) ||
648 (pred_bb->data_flow_info->ending_null_check_v == NULL)) {
649 continue;
650 }
buzbee862a7602013-04-05 10:58:54 -0700651 temp_ssa_register_v_->Intersect(pred_bb->data_flow_info->ending_null_check_v);
buzbee311ca162013-02-28 15:56:43 -0800652 }
653 }
654
655 // Walk through the instruction in the block, updating as necessary
656 for (MIR* mir = bb->first_mir_insn; mir != NULL; mir = mir->next) {
657 if (mir->ssa_rep == NULL) {
658 continue;
659 }
buzbee1fd33462013-03-25 13:40:45 -0700660 int df_attributes = oat_data_flow_attributes_[mir->dalvikInsn.opcode];
buzbee311ca162013-02-28 15:56:43 -0800661
662 // Mark target of NEW* as non-null
663 if (df_attributes & DF_NON_NULL_DST) {
buzbee862a7602013-04-05 10:58:54 -0700664 temp_ssa_register_v_->SetBit(mir->ssa_rep->defs[0]);
buzbee311ca162013-02-28 15:56:43 -0800665 }
666
667 // Mark non-null returns from invoke-style NEW*
668 if (df_attributes & DF_NON_NULL_RET) {
669 MIR* next_mir = mir->next;
670 // Next should be an MOVE_RESULT_OBJECT
671 if (next_mir &&
672 next_mir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
673 // Mark as null checked
buzbee862a7602013-04-05 10:58:54 -0700674 temp_ssa_register_v_->SetBit(next_mir->ssa_rep->defs[0]);
buzbee311ca162013-02-28 15:56:43 -0800675 } else {
676 if (next_mir) {
677 LOG(WARNING) << "Unexpected opcode following new: " << next_mir->dalvikInsn.opcode;
678 } else if (bb->fall_through) {
679 // Look in next basic block
680 struct BasicBlock* next_bb = bb->fall_through;
681 for (MIR* tmir = next_bb->first_mir_insn; tmir != NULL;
682 tmir =tmir->next) {
683 if (static_cast<int>(tmir->dalvikInsn.opcode) >= static_cast<int>(kMirOpFirst)) {
684 continue;
685 }
686 // First non-pseudo should be MOVE_RESULT_OBJECT
687 if (tmir->dalvikInsn.opcode == Instruction::MOVE_RESULT_OBJECT) {
688 // Mark as null checked
buzbee862a7602013-04-05 10:58:54 -0700689 temp_ssa_register_v_->SetBit(tmir->ssa_rep->defs[0]);
buzbee311ca162013-02-28 15:56:43 -0800690 } else {
691 LOG(WARNING) << "Unexpected op after new: " << tmir->dalvikInsn.opcode;
692 }
693 break;
694 }
695 }
696 }
697 }
698
699 /*
700 * Propagate nullcheck state on register copies (including
701 * Phi pseudo copies. For the latter, nullcheck state is
702 * the "and" of all the Phi's operands.
703 */
704 if (df_attributes & (DF_NULL_TRANSFER_0 | DF_NULL_TRANSFER_N)) {
705 int tgt_sreg = mir->ssa_rep->defs[0];
706 int operands = (df_attributes & DF_NULL_TRANSFER_0) ? 1 :
707 mir->ssa_rep->num_uses;
708 bool null_checked = true;
709 for (int i = 0; i < operands; i++) {
buzbee862a7602013-04-05 10:58:54 -0700710 null_checked &= temp_ssa_register_v_->IsBitSet(mir->ssa_rep->uses[i]);
buzbee311ca162013-02-28 15:56:43 -0800711 }
712 if (null_checked) {
buzbee862a7602013-04-05 10:58:54 -0700713 temp_ssa_register_v_->SetBit(tgt_sreg);
buzbee311ca162013-02-28 15:56:43 -0800714 }
715 }
716
717 // Already nullchecked?
718 if ((df_attributes & DF_HAS_NULL_CHKS) && !(mir->optimization_flags & MIR_IGNORE_NULL_CHECK)) {
719 int src_idx;
720 if (df_attributes & DF_NULL_CHK_1) {
721 src_idx = 1;
722 } else if (df_attributes & DF_NULL_CHK_2) {
723 src_idx = 2;
724 } else {
725 src_idx = 0;
726 }
727 int src_sreg = mir->ssa_rep->uses[src_idx];
buzbee862a7602013-04-05 10:58:54 -0700728 if (temp_ssa_register_v_->IsBitSet(src_sreg)) {
buzbee311ca162013-02-28 15:56:43 -0800729 // Eliminate the null check
730 mir->optimization_flags |= MIR_IGNORE_NULL_CHECK;
731 } else {
732 // Mark s_reg as null-checked
buzbee862a7602013-04-05 10:58:54 -0700733 temp_ssa_register_v_->SetBit(src_sreg);
buzbee311ca162013-02-28 15:56:43 -0800734 }
735 }
736 }
737
738 // Did anything change?
buzbee862a7602013-04-05 10:58:54 -0700739 bool changed = !temp_ssa_register_v_->Equal(bb->data_flow_info->ending_null_check_v);
740 if (changed) {
741 bb->data_flow_info->ending_null_check_v->Copy(temp_ssa_register_v_);
buzbee311ca162013-02-28 15:56:43 -0800742 }
buzbee862a7602013-04-05 10:58:54 -0700743 return changed;
buzbee311ca162013-02-28 15:56:43 -0800744}
745
746void MIRGraph::NullCheckElimination()
747{
748 if (!(cu_->disable_opt & (1 << kNullCheckElimination))) {
749 DCHECK(temp_ssa_register_v_ != NULL);
buzbee0665fe02013-03-21 12:32:21 -0700750 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800751 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
752 NullCheckEliminationInit(bb);
753 }
buzbee0665fe02013-03-21 12:32:21 -0700754 PreOrderDfsIterator iter2(this, true /* iterative */);
buzbee311ca162013-02-28 15:56:43 -0800755 bool change = false;
756 for (BasicBlock* bb = iter2.Next(change); bb != NULL; bb = iter2.Next(change)) {
757 change = EliminateNullChecks(bb);
758 }
759 }
760 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
761 DumpCFG("/sdcard/4_post_nce_cfg/", false);
762 }
763}
764
765void MIRGraph::BasicBlockCombine()
766{
buzbee0665fe02013-03-21 12:32:21 -0700767 PreOrderDfsIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800768 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
769 CombineBlocks(bb);
770 }
771 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
772 DumpCFG("/sdcard/5_post_bbcombine_cfg/", false);
773 }
774}
775
776void MIRGraph::CodeLayout()
777{
buzbee1fd33462013-03-25 13:40:45 -0700778 if (cu_->enable_debug & (1 << kDebugVerifyDataflow)) {
779 VerifyDataflow();
780 }
buzbee0665fe02013-03-21 12:32:21 -0700781 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800782 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
783 LayoutBlocks(bb);
784 }
785 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
786 DumpCFG("/sdcard/2_post_layout_cfg/", true);
787 }
788}
789
790void MIRGraph::DumpCheckStats()
791{
792 Checkstats* stats =
buzbee862a7602013-04-05 10:58:54 -0700793 static_cast<Checkstats*>(arena_->NewMem(sizeof(Checkstats), true,
794 ArenaAllocator::kAllocDFInfo));
buzbee1fd33462013-03-25 13:40:45 -0700795 checkstats_ = stats;
buzbee0665fe02013-03-21 12:32:21 -0700796 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800797 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
798 CountChecks(bb);
799 }
800 if (stats->null_checks > 0) {
801 float eliminated = static_cast<float>(stats->null_checks_eliminated);
802 float checks = static_cast<float>(stats->null_checks);
803 LOG(INFO) << "Null Checks: " << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
804 << stats->null_checks_eliminated << " of " << stats->null_checks << " -> "
805 << (eliminated/checks) * 100.0 << "%";
806 }
807 if (stats->range_checks > 0) {
808 float eliminated = static_cast<float>(stats->range_checks_eliminated);
809 float checks = static_cast<float>(stats->range_checks);
810 LOG(INFO) << "Range Checks: " << PrettyMethod(cu_->method_idx, *cu_->dex_file) << " "
811 << stats->range_checks_eliminated << " of " << stats->range_checks << " -> "
812 << (eliminated/checks) * 100.0 << "%";
813 }
814}
815
816bool MIRGraph::BuildExtendedBBList(struct BasicBlock* bb)
817{
818 if (bb->visited) return false;
819 if (!((bb->block_type == kEntryBlock) || (bb->block_type == kDalvikByteCode)
820 || (bb->block_type == kExitBlock))) {
821 // Ignore special blocks
822 bb->visited = true;
823 return false;
824 }
825 // Must be head of extended basic block.
826 BasicBlock* start_bb = bb;
827 extended_basic_blocks_.push_back(bb);
828 bool terminated_by_return = false;
829 // Visit blocks strictly dominated by this head.
830 while (bb != NULL) {
831 bb->visited = true;
832 terminated_by_return |= bb->terminated_by_return;
833 bb = NextDominatedBlock(bb);
834 }
835 if (terminated_by_return) {
836 // This extended basic block contains a return, so mark all members.
837 bb = start_bb;
838 while (bb != NULL) {
839 bb->dominates_return = true;
840 bb = NextDominatedBlock(bb);
841 }
842 }
843 return false; // Not iterative - return value will be ignored
844}
845
846
847void MIRGraph::BasicBlockOptimization()
848{
849 if (!(cu_->disable_opt & (1 << kBBOpt))) {
buzbee311ca162013-02-28 15:56:43 -0800850 DCHECK_EQ(cu_->num_compiler_temps, 0);
851 // Mark all blocks as not visited
buzbee0665fe02013-03-21 12:32:21 -0700852 AllNodesIterator iter(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800853 for (BasicBlock* bb = iter.Next(); bb != NULL; bb = iter.Next()) {
854 ClearVisitedFlag(bb);
855 }
buzbee0665fe02013-03-21 12:32:21 -0700856 PreOrderDfsIterator iter2(this, false /* not iterative */);
buzbee311ca162013-02-28 15:56:43 -0800857 for (BasicBlock* bb = iter2.Next(); bb != NULL; bb = iter2.Next()) {
858 BuildExtendedBBList(bb);
859 }
860 // Perform extended basic block optimizations.
861 for (unsigned int i = 0; i < extended_basic_blocks_.size(); i++) {
862 BasicBlockOpt(extended_basic_blocks_[i]);
863 }
864 }
865 if (cu_->enable_debug & (1 << kDebugDumpCFG)) {
866 DumpCFG("/sdcard/6_post_bbo_cfg/", false);
867 }
868}
869
870} // namespace art