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