1 /* 2 * Copyright (C) 2014 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 <vector> 18 19 #include "base/logging.h" 20 #include "dataflow_iterator.h" 21 #include "dataflow_iterator-inl.h" 22 #include "dex/compiler_ir.h" 23 #include "dex/mir_field_info.h" 24 #include "gtest/gtest.h" 25 26 namespace art { 27 28 class MirOptimizationTest : public testing::Test { 29 protected: 30 struct BBDef { 31 static constexpr size_t kMaxSuccessors = 4; 32 static constexpr size_t kMaxPredecessors = 4; 33 34 BBType type; 35 size_t num_successors; 36 BasicBlockId successors[kMaxPredecessors]; 37 size_t num_predecessors; 38 BasicBlockId predecessors[kMaxPredecessors]; 39 }; 40 41 struct MethodDef { 42 uint16_t method_idx; 43 uintptr_t declaring_dex_file; 44 uint16_t declaring_class_idx; 45 uint16_t declaring_method_idx; 46 InvokeType invoke_type; 47 InvokeType sharp_type; 48 bool is_referrers_class; 49 bool is_initialized; 50 }; 51 52 struct MIRDef { 53 BasicBlockId bbid; 54 Instruction::Code opcode; 55 uint32_t field_or_method_info; 56 uint32_t vA; 57 uint32_t vB; 58 uint32_t vC; 59 }; 60 61 #define DEF_SUCC0() \ 62 0u, { } 63 #define DEF_SUCC1(s1) \ 64 1u, { s1 } 65 #define DEF_SUCC2(s1, s2) \ 66 2u, { s1, s2 } 67 #define DEF_SUCC3(s1, s2, s3) \ 68 3u, { s1, s2, s3 } 69 #define DEF_SUCC4(s1, s2, s3, s4) \ 70 4u, { s1, s2, s3, s4 } 71 #define DEF_PRED0() \ 72 0u, { } 73 #define DEF_PRED1(p1) \ 74 1u, { p1 } 75 #define DEF_PRED2(p1, p2) \ 76 2u, { p1, p2 } 77 #define DEF_PRED3(p1, p2, p3) \ 78 3u, { p1, p2, p3 } 79 #define DEF_PRED4(p1, p2, p3, p4) \ 80 4u, { p1, p2, p3, p4 } 81 #define DEF_BB(type, succ, pred) \ 82 { type, succ, pred } 83 84 #define DEF_SGET_SPUT(bb, opcode, vA, field_info) \ 85 { bb, opcode, field_info, vA, 0u, 0u } 86 #define DEF_IGET_IPUT(bb, opcode, vA, vB, field_info) \ 87 { bb, opcode, field_info, vA, vB, 0u } 88 #define DEF_AGET_APUT(bb, opcode, vA, vB, vC) \ 89 { bb, opcode, 0u, vA, vB, vC } 90 #define DEF_INVOKE(bb, opcode, vC, method_info) \ 91 { bb, opcode, method_info, 0u, 0u, vC } 92 #define DEF_OTHER0(bb, opcode) \ 93 { bb, opcode, 0u, 0u, 0u, 0u } 94 #define DEF_OTHER1(bb, opcode, vA) \ 95 { bb, opcode, 0u, vA, 0u, 0u } 96 #define DEF_OTHER2(bb, opcode, vA, vB) \ 97 { bb, opcode, 0u, vA, vB, 0u } 98 99 void DoPrepareBasicBlocks(const BBDef* defs, size_t count) { 100 cu_.mir_graph->block_id_map_.clear(); 101 cu_.mir_graph->block_list_.clear(); 102 ASSERT_LT(3u, count); // null, entry, exit and at least one bytecode block. 103 ASSERT_EQ(kNullBlock, defs[0].type); 104 ASSERT_EQ(kEntryBlock, defs[1].type); 105 ASSERT_EQ(kExitBlock, defs[2].type); 106 for (size_t i = 0u; i != count; ++i) { 107 const BBDef* def = &defs[i]; 108 BasicBlock* bb = cu_.mir_graph->CreateNewBB(def->type); 109 if (def->num_successors <= 2) { 110 bb->successor_block_list_type = kNotUsed; 111 bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u; 112 bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u; 113 } else { 114 bb->successor_block_list_type = kPackedSwitch; 115 bb->fall_through = 0u; 116 bb->taken = 0u; 117 bb->successor_blocks.reserve(def->num_successors); 118 for (size_t j = 0u; j != def->num_successors; ++j) { 119 SuccessorBlockInfo* successor_block_info = 120 static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), 121 kArenaAllocSuccessor)); 122 successor_block_info->block = j; 123 successor_block_info->key = 0u; // Not used by class init check elimination. 124 bb->successor_blocks.push_back(successor_block_info); 125 } 126 } 127 bb->predecessors.assign(def->predecessors, def->predecessors + def->num_predecessors); 128 if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) { 129 bb->data_flow_info = static_cast<BasicBlockDataFlow*>( 130 cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo)); 131 } 132 } 133 ASSERT_EQ(count, cu_.mir_graph->block_list_.size()); 134 cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_[1]; 135 ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type); 136 cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_[2]; 137 ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type); 138 } 139 140 template <size_t count> 141 void PrepareBasicBlocks(const BBDef (&defs)[count]) { 142 DoPrepareBasicBlocks(defs, count); 143 } 144 145 void PrepareSingleBlock() { 146 static const BBDef bbs[] = { 147 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 148 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 149 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)), 150 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)), 151 }; 152 PrepareBasicBlocks(bbs); 153 } 154 155 void PrepareDiamond() { 156 static const BBDef bbs[] = { 157 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 158 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 159 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 160 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), 161 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), 162 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), 163 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), 164 }; 165 PrepareBasicBlocks(bbs); 166 } 167 168 void PrepareLoop() { 169 static const BBDef bbs[] = { 170 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 171 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 172 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 173 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 174 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)), // "taken" loops to self. 175 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 176 }; 177 PrepareBasicBlocks(bbs); 178 } 179 180 void PrepareNestedLoopsWhile_While() { 181 static const BBDef bbs[] = { 182 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 183 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 184 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(8)), 185 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 186 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 8), DEF_PRED2(3, 7)), // Outer while loop head. 187 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)), // Inner while loop head. 188 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)), // "taken" loops to inner head. 189 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(5)), // "taken" loops to outer head. 190 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 191 }; 192 PrepareBasicBlocks(bbs); 193 } 194 195 void PrepareNestedLoopsWhile_WhileWhile() { 196 static const BBDef bbs[] = { 197 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 198 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 199 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(10)), 200 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 201 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 10), DEF_PRED2(3, 9)), // Outer while loop head. 202 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)), // Inner while loop head 1. 203 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)), // Loops to inner head 1. 204 DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED2(5, 8)), // Inner while loop head 2. 205 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(7)), // loops to inner head 2. 206 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(7)), // loops to outer head. 207 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 208 }; 209 PrepareBasicBlocks(bbs); 210 } 211 212 void PrepareNestedLoopsWhile_WhileWhile_WithExtraEdge() { 213 // Extra edge from the first inner loop body to second inner loop body (6u->8u). 214 static const BBDef bbs[] = { 215 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 216 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 217 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(10)), 218 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 219 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 10), DEF_PRED2(3, 9)), // Outer while loop head. 220 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)), // Inner while loop head 1. 221 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 8), DEF_PRED1(5)), // Loops to inner head 1. 222 DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED2(5, 8)), // Inner while loop head 2. 223 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED2(7, 6)), // loops to inner head 2. 224 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(7)), // loops to outer head. 225 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 226 }; 227 PrepareBasicBlocks(bbs); 228 } 229 230 void PrepareCatch() { 231 static const BBDef bbs[] = { 232 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 233 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 234 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 235 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), // The top. 236 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // The throwing insn. 237 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Catch handler. 238 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // The merged block. 239 }; 240 PrepareBasicBlocks(bbs); 241 BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u); 242 catch_handler->catch_entry = true; 243 // Add successor block info to the check block. 244 BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); 245 check_bb->successor_block_list_type = kCatch; 246 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 247 (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 248 successor_block_info->block = catch_handler->id; 249 check_bb->successor_blocks.push_back(successor_block_info); 250 } 251 252 void DoPrepareMethods(const MethodDef* defs, size_t count) { 253 cu_.mir_graph->method_lowering_infos_.clear(); 254 cu_.mir_graph->method_lowering_infos_.reserve(count); 255 for (size_t i = 0u; i != count; ++i) { 256 const MethodDef* def = &defs[i]; 257 MirMethodLoweringInfo method_info(def->method_idx, def->invoke_type, false); 258 if (def->declaring_dex_file != 0u) { 259 method_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 260 method_info.declaring_class_idx_ = def->declaring_class_idx; 261 method_info.declaring_method_idx_ = def->declaring_method_idx; 262 } 263 ASSERT_EQ(def->invoke_type != kStatic, def->sharp_type != kStatic); 264 method_info.flags_ = 265 ((def->invoke_type == kStatic) ? MirMethodLoweringInfo::kFlagIsStatic : 0u) | 266 MirMethodLoweringInfo::kFlagFastPath | 267 (static_cast<uint16_t>(def->invoke_type) << MirMethodLoweringInfo::kBitInvokeTypeBegin) | 268 (static_cast<uint16_t>(def->sharp_type) << MirMethodLoweringInfo::kBitSharpTypeBegin) | 269 ((def->is_referrers_class) ? MirMethodLoweringInfo::kFlagIsReferrersClass : 0u) | 270 ((def->is_initialized == kStatic) ? MirMethodLoweringInfo::kFlagClassIsInitialized : 0u); 271 ASSERT_EQ(def->declaring_dex_file != 0u, method_info.IsResolved()); 272 cu_.mir_graph->method_lowering_infos_.push_back(method_info); 273 } 274 } 275 276 template <size_t count> 277 void PrepareMethods(const MethodDef (&defs)[count]) { 278 DoPrepareMethods(defs, count); 279 } 280 281 void DoPrepareMIRs(const MIRDef* defs, size_t count) { 282 mir_count_ = count; 283 mirs_ = cu_.arena.AllocArray<MIR>(count, kArenaAllocMIR); 284 uint64_t merged_df_flags = 0u; 285 for (size_t i = 0u; i != count; ++i) { 286 const MIRDef* def = &defs[i]; 287 MIR* mir = &mirs_[i]; 288 mir->dalvikInsn.opcode = def->opcode; 289 ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.size()); 290 BasicBlock* bb = cu_.mir_graph->block_list_[def->bbid]; 291 bb->AppendMIR(mir); 292 if (IsInstructionIGetOrIPut(def->opcode)) { 293 ASSERT_LT(def->field_or_method_info, cu_.mir_graph->ifield_lowering_infos_.size()); 294 mir->meta.ifield_lowering_info = def->field_or_method_info; 295 ASSERT_EQ(cu_.mir_graph->ifield_lowering_infos_[def->field_or_method_info].MemAccessType(), 296 IGetOrIPutMemAccessType(def->opcode)); 297 } else if (IsInstructionSGetOrSPut(def->opcode)) { 298 ASSERT_LT(def->field_or_method_info, cu_.mir_graph->sfield_lowering_infos_.size()); 299 mir->meta.sfield_lowering_info = def->field_or_method_info; 300 ASSERT_EQ(cu_.mir_graph->sfield_lowering_infos_[def->field_or_method_info].MemAccessType(), 301 SGetOrSPutMemAccessType(def->opcode)); 302 } else if (IsInstructionInvoke(def->opcode)) { 303 ASSERT_LT(def->field_or_method_info, cu_.mir_graph->method_lowering_infos_.size()); 304 mir->meta.method_lowering_info = def->field_or_method_info; 305 } 306 mir->dalvikInsn.vA = def->vA; 307 mir->dalvikInsn.vB = def->vB; 308 mir->dalvikInsn.vC = def->vC; 309 mir->ssa_rep = nullptr; 310 mir->offset = 2 * i; // All insns need to be at least 2 code units long. 311 mir->optimization_flags = 0u; 312 merged_df_flags |= MIRGraph::GetDataFlowAttributes(def->opcode); 313 } 314 cu_.mir_graph->merged_df_flags_ = merged_df_flags; 315 316 code_item_ = static_cast<DexFile::CodeItem*>( 317 cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc)); 318 memset(code_item_, 0, sizeof(DexFile::CodeItem)); 319 code_item_->insns_size_in_code_units_ = 2u * count; 320 cu_.mir_graph->current_code_item_ = code_item_; 321 } 322 323 template <size_t count> 324 void PrepareMIRs(const MIRDef (&defs)[count]) { 325 DoPrepareMIRs(defs, count); 326 } 327 328 MirOptimizationTest() 329 : pool_(), 330 cu_(&pool_, kRuntimeISA, nullptr, nullptr), 331 mir_count_(0u), 332 mirs_(nullptr), 333 code_item_(nullptr) { 334 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena)); 335 cu_.access_flags = kAccStatic; // Don't let "this" interfere with this test. 336 } 337 338 ArenaPool pool_; 339 CompilationUnit cu_; 340 size_t mir_count_; 341 MIR* mirs_; 342 DexFile::CodeItem* code_item_; 343 }; 344 345 class ClassInitCheckEliminationTest : public MirOptimizationTest { 346 protected: 347 struct SFieldDef { 348 uint16_t field_idx; 349 uintptr_t declaring_dex_file; 350 uint16_t declaring_class_idx; 351 uint16_t declaring_field_idx; 352 DexMemAccessType type; 353 }; 354 355 void DoPrepareSFields(const SFieldDef* defs, size_t count) { 356 cu_.mir_graph->sfield_lowering_infos_.clear(); 357 cu_.mir_graph->sfield_lowering_infos_.reserve(count); 358 for (size_t i = 0u; i != count; ++i) { 359 const SFieldDef* def = &defs[i]; 360 MirSFieldLoweringInfo field_info(def->field_idx, def->type); 361 if (def->declaring_dex_file != 0u) { 362 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 363 field_info.declaring_class_idx_ = def->declaring_class_idx; 364 field_info.declaring_field_idx_ = def->declaring_field_idx; 365 // We don't care about the volatile flag in these tests. 366 } 367 ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved()); 368 ASSERT_FALSE(field_info.IsClassInitialized()); 369 cu_.mir_graph->sfield_lowering_infos_.push_back(field_info); 370 } 371 } 372 373 template <size_t count> 374 void PrepareSFields(const SFieldDef (&defs)[count]) { 375 DoPrepareSFields(defs, count); 376 } 377 378 void PerformClassInitCheckElimination() { 379 cu_.mir_graph->ComputeDFSOrders(); 380 bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate(); 381 ASSERT_TRUE(gate_result); 382 RepeatingPreOrderDfsIterator iterator(cu_.mir_graph.get()); 383 bool change = false; 384 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) { 385 change = cu_.mir_graph->EliminateClassInitChecks(bb); 386 } 387 cu_.mir_graph->EliminateClassInitChecksEnd(); 388 } 389 390 ClassInitCheckEliminationTest() 391 : MirOptimizationTest() { 392 } 393 }; 394 395 class NullCheckEliminationTest : public MirOptimizationTest { 396 protected: 397 struct IFieldDef { 398 uint16_t field_idx; 399 uintptr_t declaring_dex_file; 400 uint16_t declaring_class_idx; 401 uint16_t declaring_field_idx; 402 DexMemAccessType type; 403 }; 404 405 void DoPrepareIFields(const IFieldDef* defs, size_t count) { 406 cu_.mir_graph->ifield_lowering_infos_.clear(); 407 cu_.mir_graph->ifield_lowering_infos_.reserve(count); 408 for (size_t i = 0u; i != count; ++i) { 409 const IFieldDef* def = &defs[i]; 410 MirIFieldLoweringInfo field_info(def->field_idx, def->type, false); 411 if (def->declaring_dex_file != 0u) { 412 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 413 field_info.declaring_class_idx_ = def->declaring_class_idx; 414 field_info.declaring_field_idx_ = def->declaring_field_idx; 415 // We don't care about the volatile flag in these tests. 416 } 417 ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved()); 418 cu_.mir_graph->ifield_lowering_infos_.push_back(field_info); 419 } 420 } 421 422 template <size_t count> 423 void PrepareIFields(const IFieldDef (&defs)[count]) { 424 DoPrepareIFields(defs, count); 425 } 426 427 void PerformNullCheckElimination() { 428 // Make vregs in range [100, 1000) input registers, i.e. requiring a null check. 429 code_item_->registers_size_ = 1000; 430 code_item_->ins_size_ = 900; 431 432 cu_.mir_graph->ComputeDFSOrders(); 433 bool gate_result = cu_.mir_graph->EliminateNullChecksGate(); 434 ASSERT_TRUE(gate_result); 435 RepeatingPreOrderDfsIterator iterator(cu_.mir_graph.get()); 436 bool change = false; 437 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) { 438 change = cu_.mir_graph->EliminateNullChecks(bb); 439 } 440 cu_.mir_graph->EliminateNullChecksEnd(); 441 } 442 443 NullCheckEliminationTest() 444 : MirOptimizationTest() { 445 static const MethodDef methods[] = { 446 { 0u, 1u, 0u, 0u, kDirect, kDirect, false, false }, // Dummy. 447 }; 448 PrepareMethods(methods); 449 } 450 }; 451 452 class SuspendCheckEliminationTest : public MirOptimizationTest { 453 protected: 454 bool IsBackEdge(BasicBlockId branch_bb, BasicBlockId target_bb) { 455 BasicBlock* branch = cu_.mir_graph->GetBasicBlock(branch_bb); 456 return target_bb != NullBasicBlockId && cu_.mir_graph->IsBackEdge(branch, target_bb); 457 } 458 459 bool IsSuspendCheckEdge(BasicBlockId branch_bb, BasicBlockId target_bb) { 460 BasicBlock* branch = cu_.mir_graph->GetBasicBlock(branch_bb); 461 return cu_.mir_graph->IsSuspendCheckEdge(branch, target_bb); 462 } 463 464 void PerformSuspendCheckElimination() { 465 cu_.mir_graph->SSATransformationStart(); 466 cu_.mir_graph->ComputeDFSOrders(); 467 cu_.mir_graph->ComputeDominators(); 468 cu_.mir_graph->ComputeTopologicalSortOrder(); 469 cu_.mir_graph->SSATransformationEnd(); 470 471 bool gate_result = cu_.mir_graph->EliminateSuspendChecksGate(); 472 ASSERT_NE(gate_result, kLeafOptimization); 473 if (kLeafOptimization) { 474 // Even with kLeafOptimization on and Gate() refusing to allow SCE, we want 475 // to run the SCE test to avoid bitrot, so we need to initialize explicitly. 476 cu_.mir_graph->suspend_checks_in_loops_ = 477 cu_.mir_graph->arena_->AllocArray<uint32_t>(cu_.mir_graph->GetNumBlocks(), 478 kArenaAllocMisc); 479 } 480 481 TopologicalSortIterator iterator(cu_.mir_graph.get()); 482 bool change = false; 483 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) { 484 change = cu_.mir_graph->EliminateSuspendChecks(bb); 485 } 486 } 487 488 SuspendCheckEliminationTest() 489 : MirOptimizationTest() { 490 static const MethodDef methods[] = { 491 { 0u, 1u, 0u, 0u, kDirect, kDirect, false, false }, // Dummy. 492 }; 493 PrepareMethods(methods); 494 } 495 }; 496 497 TEST_F(ClassInitCheckEliminationTest, SingleBlock) { 498 static const SFieldDef sfields[] = { 499 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 500 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 501 { 2u, 1u, 2u, 2u, kDexMemAccessWord }, 502 { 3u, 1u, 3u, 3u, kDexMemAccessWord }, // Same declaring class as sfield[4]. 503 { 4u, 1u, 3u, 4u, kDexMemAccessWord }, // Same declaring class as sfield[3]. 504 { 5u, 0u, 0u, 0u, kDexMemAccessWord }, // Unresolved. 505 }; 506 static const MIRDef mirs[] = { 507 DEF_SGET_SPUT(3u, Instruction::SPUT, 0u, 5u), // Unresolved. 508 DEF_SGET_SPUT(3u, Instruction::SPUT, 0u, 0u), 509 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 1u), 510 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 2u), 511 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 5u), // Unresolved. 512 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 0u), 513 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 1u), 514 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 2u), 515 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 5u), // Unresolved. 516 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 3u), 517 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 4u), 518 }; 519 static const bool expected_ignore_clinit_check[] = { 520 false, false, false, false, true, true, true, true, true, false, true 521 }; 522 523 PrepareSFields(sfields); 524 PrepareSingleBlock(); 525 PrepareMIRs(mirs); 526 PerformClassInitCheckElimination(); 527 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 528 for (size_t i = 0u; i != arraysize(mirs); ++i) { 529 EXPECT_EQ(expected_ignore_clinit_check[i], 530 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 531 EXPECT_EQ(expected_ignore_clinit_check[i], 532 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 533 } 534 } 535 536 TEST_F(ClassInitCheckEliminationTest, SingleBlockWithInvokes) { 537 static const SFieldDef sfields[] = { 538 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 539 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 540 { 2u, 1u, 2u, 2u, kDexMemAccessWord }, 541 }; 542 static const MethodDef methods[] = { 543 { 0u, 1u, 0u, 0u, kStatic, kStatic, false, false }, 544 { 1u, 1u, 1u, 1u, kStatic, kStatic, false, false }, 545 { 2u, 1u, 2u, 2u, kStatic, kStatic, false, false }, 546 }; 547 static const MIRDef mirs[] = { 548 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 0u), 549 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 0u), 550 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 1u), 551 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 1u), 552 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 2u), 553 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 2u), 554 }; 555 static const bool expected_class_initialized[] = { 556 false, true, false, true, false, true 557 }; 558 static const bool expected_class_in_dex_cache[] = { 559 false, false, false, false, false, false 560 }; 561 562 PrepareSFields(sfields); 563 PrepareMethods(methods); 564 PrepareSingleBlock(); 565 PrepareMIRs(mirs); 566 PerformClassInitCheckElimination(); 567 ASSERT_EQ(arraysize(expected_class_initialized), mir_count_); 568 ASSERT_EQ(arraysize(expected_class_in_dex_cache), mir_count_); 569 for (size_t i = 0u; i != arraysize(mirs); ++i) { 570 EXPECT_EQ(expected_class_initialized[i], 571 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 572 EXPECT_EQ(expected_class_in_dex_cache[i], 573 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 574 } 575 } 576 577 TEST_F(ClassInitCheckEliminationTest, Diamond) { 578 static const SFieldDef sfields[] = { 579 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 580 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 581 { 2u, 1u, 2u, 2u, kDexMemAccessWord }, 582 { 3u, 1u, 3u, 3u, kDexMemAccessWord }, 583 { 4u, 1u, 4u, 4u, kDexMemAccessWord }, 584 { 5u, 1u, 5u, 5u, kDexMemAccessWord }, 585 { 6u, 1u, 6u, 6u, kDexMemAccessWord }, 586 { 7u, 1u, 7u, 7u, kDexMemAccessWord }, 587 { 8u, 1u, 8u, 8u, kDexMemAccessWord }, // Same declaring class as sfield[9]. 588 { 9u, 1u, 8u, 9u, kDexMemAccessWord }, // Same declaring class as sfield[8]. 589 { 10u, 0u, 0u, 0u, kDexMemAccessWord }, // Unresolved. 590 }; 591 static const MIRDef mirs[] = { 592 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 593 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 10u), // Unresolved. 594 DEF_SGET_SPUT(3u, Instruction::SPUT, 0u, 10u), // Unresolved. 595 DEF_SGET_SPUT(3u, Instruction::SPUT, 0u, 0u), 596 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 0u), // Eliminated (BB #3 dominates #6). 597 DEF_SGET_SPUT(4u, Instruction::SPUT, 0u, 1u), 598 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 1u), // Not eliminated (BB #4 doesn't dominate #6). 599 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 2u), 600 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 2u), // Eliminated (BB #3 dominates #4). 601 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 3u), 602 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 3u), // Eliminated (BB #3 dominates #5). 603 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 4u), 604 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 4u), // Eliminated (BB #3 dominates #6). 605 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 5u), 606 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 5u), // Not eliminated (BB #4 doesn't dominate #6). 607 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 6u), 608 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 6u), // Not eliminated (BB #5 doesn't dominate #6). 609 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 7u), 610 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 7u), 611 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 7u), // Eliminated (initialized in both #3 and #4). 612 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 8u), 613 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 9u), 614 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 8u), // Eliminated (with sfield[9] in BB #5). 615 DEF_SGET_SPUT(6u, Instruction::SPUT, 0u, 9u), // Eliminated (with sfield[8] in BB #4). 616 }; 617 static const bool expected_ignore_clinit_check[] = { 618 false, true, // Unresolved: sfield[10] 619 false, true, // sfield[0] 620 false, false, // sfield[1] 621 false, true, // sfield[2] 622 false, true, // sfield[3] 623 false, true, // sfield[4] 624 false, false, // sfield[5] 625 false, false, // sfield[6] 626 false, false, true, // sfield[7] 627 false, false, true, true, // sfield[8], sfield[9] 628 }; 629 630 PrepareSFields(sfields); 631 PrepareDiamond(); 632 PrepareMIRs(mirs); 633 PerformClassInitCheckElimination(); 634 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 635 for (size_t i = 0u; i != arraysize(mirs); ++i) { 636 EXPECT_EQ(expected_ignore_clinit_check[i], 637 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 638 EXPECT_EQ(expected_ignore_clinit_check[i], 639 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 640 } 641 } 642 643 TEST_F(ClassInitCheckEliminationTest, DiamondWithInvokes) { 644 static const SFieldDef sfields[] = { 645 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 646 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 647 { 2u, 1u, 2u, 2u, kDexMemAccessWord }, 648 { 3u, 1u, 3u, 3u, kDexMemAccessWord }, 649 { 4u, 1u, 4u, 4u, kDexMemAccessWord }, 650 }; 651 static const MethodDef methods[] = { 652 { 0u, 1u, 0u, 0u, kStatic, kStatic, false, false }, 653 { 1u, 1u, 1u, 1u, kStatic, kStatic, false, false }, 654 { 2u, 1u, 2u, 2u, kStatic, kStatic, false, false }, 655 { 3u, 1u, 3u, 3u, kStatic, kStatic, false, false }, 656 { 4u, 1u, 4u, 4u, kStatic, kStatic, false, false }, 657 }; 658 static const MIRDef mirs[] = { 659 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 660 DEF_SGET_SPUT(3u, Instruction::SPUT, 0u, 0u), 661 DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u /* dummy */, 0u), 662 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 1u), 663 DEF_SGET_SPUT(6u, Instruction::SPUT, 0u, 1u), 664 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 2u), 665 DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u /* dummy */, 2u), 666 DEF_SGET_SPUT(6u, Instruction::SPUT, 0u, 2u), 667 DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u /* dummy */, 3u), 668 DEF_SGET_SPUT(5u, Instruction::SPUT, 0u, 3u), 669 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 3u), 670 DEF_SGET_SPUT(4u, Instruction::SPUT, 0u, 4u), 671 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 4u), 672 DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u /* dummy */, 4u), 673 }; 674 static const bool expected_class_initialized[] = { 675 false, true, // BB #3 SPUT, BB#6 INVOKE_STATIC 676 false, true, // BB #3 INVOKE_STATIC, BB#6 SPUT 677 false, false, true, // BB #4 SGET, BB #5 INVOKE_STATIC, BB #6 SPUT 678 false, false, true, // BB #4 INVOKE_STATIC, BB #5 SPUT, BB #6 SGET 679 false, false, true, // BB #4 SPUT, BB #5 SGET, BB #6 INVOKE_STATIC 680 }; 681 static const bool expected_class_in_dex_cache[] = { 682 false, false, // BB #3 SPUT, BB#6 INVOKE_STATIC 683 false, false, // BB #3 INVOKE_STATIC, BB#6 SPUT 684 false, false, false, // BB #4 SGET, BB #5 INVOKE_STATIC, BB #6 SPUT 685 false, false, false, // BB #4 INVOKE_STATIC, BB #5 SPUT, BB #6 SGET 686 false, false, false, // BB #4 SPUT, BB #5 SGET, BB #6 INVOKE_STATIC 687 }; 688 689 PrepareSFields(sfields); 690 PrepareMethods(methods); 691 PrepareDiamond(); 692 PrepareMIRs(mirs); 693 PerformClassInitCheckElimination(); 694 ASSERT_EQ(arraysize(expected_class_initialized), mir_count_); 695 ASSERT_EQ(arraysize(expected_class_in_dex_cache), mir_count_); 696 for (size_t i = 0u; i != arraysize(mirs); ++i) { 697 EXPECT_EQ(expected_class_initialized[i], 698 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 699 EXPECT_EQ(expected_class_in_dex_cache[i], 700 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 701 } 702 } 703 704 TEST_F(ClassInitCheckEliminationTest, Loop) { 705 static const SFieldDef sfields[] = { 706 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 707 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 708 { 2u, 1u, 2u, 2u, kDexMemAccessWord }, 709 }; 710 static const MIRDef mirs[] = { 711 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 0u), 712 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 0u), // Eliminated. 713 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 1u), 714 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 1u), // Eliminated. 715 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 2u), 716 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 2u), // Eliminated. 717 }; 718 static const bool expected_ignore_clinit_check[] = { 719 false, true, false, true, false, true, 720 }; 721 722 PrepareSFields(sfields); 723 PrepareLoop(); 724 PrepareMIRs(mirs); 725 PerformClassInitCheckElimination(); 726 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 727 for (size_t i = 0u; i != arraysize(mirs); ++i) { 728 EXPECT_EQ(expected_ignore_clinit_check[i], 729 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 730 EXPECT_EQ(expected_ignore_clinit_check[i], 731 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 732 } 733 } 734 735 TEST_F(ClassInitCheckEliminationTest, LoopWithInvokes) { 736 static const SFieldDef sfields[] = { 737 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 738 }; 739 static const MethodDef methods[] = { 740 { 0u, 1u, 0u, 0u, kStatic, kStatic, false, false }, 741 { 1u, 1u, 1u, 1u, kStatic, kStatic, false, false }, 742 { 2u, 1u, 2u, 2u, kStatic, kStatic, false, false }, 743 }; 744 static const MIRDef mirs[] = { 745 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 0u), 746 DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u /* dummy */, 0u), 747 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u /* dummy */, 1u), 748 DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u /* dummy */, 1u), 749 DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u /* dummy */, 2u), 750 DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u /* dummy */, 2u), 751 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 0u), 752 }; 753 static const bool expected_class_initialized[] = { 754 false, true, false, true, false, true, true, 755 }; 756 static const bool expected_class_in_dex_cache[] = { 757 false, false, false, false, false, false, false, 758 }; 759 760 PrepareSFields(sfields); 761 PrepareMethods(methods); 762 PrepareLoop(); 763 PrepareMIRs(mirs); 764 PerformClassInitCheckElimination(); 765 ASSERT_EQ(arraysize(expected_class_initialized), mir_count_); 766 ASSERT_EQ(arraysize(expected_class_in_dex_cache), mir_count_); 767 for (size_t i = 0u; i != arraysize(mirs); ++i) { 768 EXPECT_EQ(expected_class_initialized[i], 769 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 770 EXPECT_EQ(expected_class_in_dex_cache[i], 771 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 772 } 773 } 774 775 TEST_F(ClassInitCheckEliminationTest, Catch) { 776 static const SFieldDef sfields[] = { 777 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 778 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 779 { 2u, 1u, 2u, 2u, kDexMemAccessWord }, 780 { 3u, 1u, 3u, 3u, kDexMemAccessWord }, 781 }; 782 static const MIRDef mirs[] = { 783 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 0u), // Before the exception edge. 784 DEF_SGET_SPUT(3u, Instruction::SGET, 0u, 1u), // Before the exception edge. 785 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 2u), // After the exception edge. 786 DEF_SGET_SPUT(4u, Instruction::SGET, 0u, 3u), // After the exception edge. 787 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 0u), // In catch handler; eliminated. 788 DEF_SGET_SPUT(5u, Instruction::SGET, 0u, 2u), // In catch handler; not eliminated. 789 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 0u), // Class init check eliminated. 790 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 1u), // Class init check eliminated. 791 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 2u), // Class init check eliminated. 792 DEF_SGET_SPUT(6u, Instruction::SGET, 0u, 3u), // Class init check not eliminated. 793 }; 794 static const bool expected_ignore_clinit_check[] = { 795 false, false, false, false, true, false, true, true, true, false 796 }; 797 798 PrepareSFields(sfields); 799 PrepareCatch(); 800 PrepareMIRs(mirs); 801 PerformClassInitCheckElimination(); 802 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 803 for (size_t i = 0u; i != arraysize(mirs); ++i) { 804 EXPECT_EQ(expected_ignore_clinit_check[i], 805 (mirs_[i].optimization_flags & MIR_CLASS_IS_INITIALIZED) != 0) << i; 806 EXPECT_EQ(expected_ignore_clinit_check[i], 807 (mirs_[i].optimization_flags & MIR_CLASS_IS_IN_DEX_CACHE) != 0) << i; 808 } 809 } 810 811 TEST_F(NullCheckEliminationTest, SingleBlock) { 812 static const IFieldDef ifields[] = { 813 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 814 { 1u, 1u, 0u, 1u, kDexMemAccessWord }, 815 { 2u, 1u, 0u, 2u, kDexMemAccessObject }, 816 }; 817 static const MIRDef mirs[] = { 818 DEF_IGET_IPUT(3u, Instruction::IGET_OBJECT, 0u, 100u, 2u), 819 DEF_IGET_IPUT(3u, Instruction::IGET, 1u, 0u, 1u), 820 DEF_IGET_IPUT(3u, Instruction::IGET_OBJECT, 2u, 100u, 2u), // Differs from 0u (no LVN here). 821 DEF_IGET_IPUT(3u, Instruction::IGET, 3u, 2u, 1u), 822 DEF_IGET_IPUT(3u, Instruction::IGET, 4u, 101u, 0u), 823 DEF_IGET_IPUT(3u, Instruction::IGET, 5u, 102u, 0u), 824 DEF_IGET_IPUT(3u, Instruction::IGET, 6u, 103u, 0u), 825 DEF_IGET_IPUT(3u, Instruction::IGET, 7u, 103u, 1u), 826 DEF_IGET_IPUT(3u, Instruction::IPUT, 8u, 104u, 0u), 827 DEF_IGET_IPUT(3u, Instruction::IPUT, 9u, 104u, 1u), 828 DEF_IGET_IPUT(3u, Instruction::IGET, 10u, 105u, 0u), 829 DEF_IGET_IPUT(3u, Instruction::IPUT, 11u, 105u, 1u), 830 DEF_IGET_IPUT(3u, Instruction::IPUT, 12u, 106u, 0u), 831 DEF_IGET_IPUT(3u, Instruction::IGET, 13u, 106u, 1u), 832 DEF_INVOKE(3u, Instruction::INVOKE_DIRECT, 107, 0u /* dummy */), 833 DEF_IGET_IPUT(3u, Instruction::IGET, 15u, 107u, 1u), 834 DEF_IGET_IPUT(3u, Instruction::IGET, 16u, 108u, 0u), 835 DEF_INVOKE(3u, Instruction::INVOKE_DIRECT, 108, 0u /* dummy */), 836 DEF_AGET_APUT(3u, Instruction::AGET, 18u, 109u, 110u), 837 DEF_AGET_APUT(3u, Instruction::APUT, 19u, 109u, 111u), 838 DEF_OTHER2(3u, Instruction::ARRAY_LENGTH, 20u, 112u), 839 DEF_AGET_APUT(3u, Instruction::AGET, 21u, 112u, 113u), 840 DEF_OTHER1(3u, Instruction::MONITOR_ENTER, 114u), 841 DEF_OTHER1(3u, Instruction::MONITOR_EXIT, 114u), 842 }; 843 static const bool expected_ignore_null_check[] = { 844 false, false, true, false /* Not doing LVN. */, 845 false, true /* Set before running NCE. */, 846 false, true, // IGET, IGET 847 false, true, // IPUT, IPUT 848 false, true, // IGET, IPUT 849 false, true, // IPUT, IGET 850 false, true, // INVOKE, IGET 851 false, true, // IGET, INVOKE 852 false, true, // AGET, APUT 853 false, true, // ARRAY_LENGTH, AGET 854 false, true, // MONITOR_ENTER, MONITOR_EXIT 855 }; 856 857 PrepareIFields(ifields); 858 PrepareSingleBlock(); 859 PrepareMIRs(mirs); 860 861 // Mark IGET 5u as null-checked to test that NCE doesn't clear this flag. 862 mirs_[5u].optimization_flags |= MIR_IGNORE_NULL_CHECK; 863 864 PerformNullCheckElimination(); 865 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 866 for (size_t i = 0u; i != arraysize(mirs); ++i) { 867 EXPECT_EQ(expected_ignore_null_check[i], 868 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 869 } 870 } 871 872 TEST_F(NullCheckEliminationTest, Diamond) { 873 static const IFieldDef ifields[] = { 874 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 875 { 1u, 1u, 0u, 1u, kDexMemAccessWord }, 876 { 2u, 1u, 0u, 2u, kDexMemAccessObject }, // int[]. 877 }; 878 static const MIRDef mirs[] = { 879 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 880 DEF_IGET_IPUT(3u, Instruction::IPUT, 0u, 100u, 0u), 881 DEF_IGET_IPUT(6u, Instruction::IGET, 1u, 100u, 1u), // Eliminated (BB #3 dominates #6). 882 DEF_IGET_IPUT(3u, Instruction::IGET, 2u, 101u, 0u), 883 DEF_IGET_IPUT(4u, Instruction::IPUT, 3u, 101u, 0u), // Eliminated (BB #3 dominates #4). 884 DEF_IGET_IPUT(3u, Instruction::IGET, 4u, 102u, 0u), 885 DEF_IGET_IPUT(5u, Instruction::IPUT, 5u, 102u, 1u), // Eliminated (BB #3 dominates #5). 886 DEF_IGET_IPUT(4u, Instruction::IPUT, 6u, 103u, 0u), 887 DEF_IGET_IPUT(6u, Instruction::IPUT, 7u, 103u, 1u), // Not eliminated (going through BB #5). 888 DEF_IGET_IPUT(5u, Instruction::IGET, 8u, 104u, 1u), 889 DEF_IGET_IPUT(6u, Instruction::IGET, 9u, 104u, 0u), // Not eliminated (going through BB #4). 890 DEF_INVOKE(4u, Instruction::INVOKE_DIRECT, 105u, 0u /* dummy */), 891 DEF_IGET_IPUT(5u, Instruction::IGET, 11u, 105u, 1u), 892 DEF_IGET_IPUT(6u, Instruction::IPUT, 12u, 105u, 0u), // Eliminated. 893 DEF_IGET_IPUT(3u, Instruction::IGET_OBJECT, 13u, 106u, 2u), 894 DEF_OTHER1(3u, Instruction::IF_EQZ, 13u), // Last insn in the BB #3. 895 DEF_OTHER2(5u, Instruction::NEW_ARRAY, 13u, 107u), 896 DEF_AGET_APUT(6u, Instruction::AGET, 16u, 13u, 108u), // Eliminated. 897 }; 898 static const bool expected_ignore_null_check[] = { 899 false, true, // BB #3 IPUT, BB #6 IGET 900 false, true, // BB #3 IGET, BB #4 IPUT 901 false, true, // BB #3 IGET, BB #5 IPUT 902 false, false, // BB #4 IPUT, BB #6 IPUT 903 false, false, // BB #5 IGET, BB #6 IGET 904 false, false, true, // BB #4 INVOKE, BB #5 IGET, BB #6 IPUT 905 false, false, // BB #3 IGET_OBJECT & IF_EQZ 906 false, true, // BB #5 NEW_ARRAY, BB #6 AGET 907 }; 908 909 PrepareIFields(ifields); 910 PrepareDiamond(); 911 PrepareMIRs(mirs); 912 PerformNullCheckElimination(); 913 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 914 for (size_t i = 0u; i != arraysize(mirs); ++i) { 915 EXPECT_EQ(expected_ignore_null_check[i], 916 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 917 } 918 } 919 920 TEST_F(NullCheckEliminationTest, Loop) { 921 static const IFieldDef ifields[] = { 922 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 923 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 924 }; 925 static const MIRDef mirs[] = { 926 DEF_IGET_IPUT(3u, Instruction::IGET, 0u, 100u, 0u), 927 DEF_IGET_IPUT(4u, Instruction::IGET, 1u, 101u, 0u), 928 DEF_IGET_IPUT(5u, Instruction::IGET, 2u, 100u, 1u), // Eliminated. 929 DEF_IGET_IPUT(5u, Instruction::IGET, 3u, 101u, 1u), // Eliminated. 930 DEF_IGET_IPUT(3u, Instruction::IGET, 4u, 102u, 0u), 931 DEF_IGET_IPUT(4u, Instruction::IGET, 5u, 102u, 1u), // Not eliminated (MOVE_OBJECT_16). 932 DEF_OTHER2(4u, Instruction::MOVE_OBJECT_16, 102u, 103u), 933 }; 934 static const bool expected_ignore_null_check[] = { 935 false, false, true, true, 936 false, false, false, 937 }; 938 939 PrepareIFields(ifields); 940 PrepareLoop(); 941 PrepareMIRs(mirs); 942 PerformNullCheckElimination(); 943 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 944 for (size_t i = 0u; i != arraysize(mirs); ++i) { 945 EXPECT_EQ(expected_ignore_null_check[i], 946 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 947 } 948 } 949 950 TEST_F(NullCheckEliminationTest, Catch) { 951 static const IFieldDef ifields[] = { 952 { 0u, 1u, 0u, 0u, kDexMemAccessWord }, 953 { 1u, 1u, 1u, 1u, kDexMemAccessWord }, 954 }; 955 static const MIRDef mirs[] = { 956 DEF_IGET_IPUT(3u, Instruction::IGET, 0u, 100u, 0u), // Before the exception edge. 957 DEF_IGET_IPUT(3u, Instruction::IGET, 1u, 101u, 0u), // Before the exception edge. 958 DEF_IGET_IPUT(4u, Instruction::IGET, 2u, 102u, 0u), // After the exception edge. 959 DEF_IGET_IPUT(4u, Instruction::IGET, 3u, 103u, 0u), // After the exception edge. 960 DEF_IGET_IPUT(5u, Instruction::IGET, 4u, 100u, 1u), // In catch handler; eliminated. 961 DEF_IGET_IPUT(5u, Instruction::IGET, 5u, 102u, 1u), // In catch handler; not eliminated. 962 DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 100u, 0u), // Null check eliminated. 963 DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 101u, 1u), // Null check eliminated. 964 DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 102u, 0u), // Null check eliminated. 965 DEF_IGET_IPUT(6u, Instruction::IGET, 6u, 103u, 1u), // Null check not eliminated. 966 }; 967 static const bool expected_ignore_null_check[] = { 968 false, false, false, false, true, false, true, true, true, false 969 }; 970 971 PrepareIFields(ifields); 972 PrepareCatch(); 973 PrepareMIRs(mirs); 974 PerformNullCheckElimination(); 975 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 976 for (size_t i = 0u; i != arraysize(mirs); ++i) { 977 EXPECT_EQ(expected_ignore_null_check[i], 978 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 979 } 980 } 981 982 TEST_F(SuspendCheckEliminationTest, LoopNoElimination) { 983 static const MIRDef mirs[] = { 984 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u, 0u), // Force the pass to run. 985 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge back. 986 }; 987 988 PrepareLoop(); 989 PrepareMIRs(mirs); 990 PerformSuspendCheckElimination(); 991 ASSERT_TRUE(IsBackEdge(4u, 4u)); 992 EXPECT_TRUE(IsSuspendCheckEdge(4u, 4u)); // Suspend point on loop to self. 993 } 994 995 TEST_F(SuspendCheckEliminationTest, LoopElimination) { 996 static const MIRDef mirs[] = { 997 DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in the loop. 998 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge back. 999 }; 1000 1001 PrepareLoop(); 1002 PrepareMIRs(mirs); 1003 PerformSuspendCheckElimination(); 1004 ASSERT_TRUE(IsBackEdge(4u, 4u)); 1005 EXPECT_FALSE(IsSuspendCheckEdge(4u, 4u)); // No suspend point on loop to self. 1006 } 1007 1008 TEST_F(SuspendCheckEliminationTest, While_While_NoElimination) { 1009 static const MIRDef mirs[] = { 1010 DEF_INVOKE(3u, Instruction::INVOKE_STATIC, 0u, 0u), // Force the pass to run. 1011 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1012 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop. 1013 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1014 DEF_OTHER0(7u, Instruction::GOTO), // Edge back to outer loop head. 1015 }; 1016 1017 PrepareNestedLoopsWhile_While(); 1018 PrepareMIRs(mirs); 1019 PerformSuspendCheckElimination(); 1020 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1021 EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u)); 1022 ASSERT_TRUE(IsBackEdge(7u, 4u)); 1023 EXPECT_TRUE(IsSuspendCheckEdge(7u, 4u)); 1024 } 1025 1026 TEST_F(SuspendCheckEliminationTest, While_While_InvokeInOuterLoopHead) { 1027 static const MIRDef mirs[] = { 1028 DEF_INVOKE(4u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in outer loop head. 1029 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1030 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop. 1031 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1032 DEF_OTHER0(7u, Instruction::GOTO), // Edge back to outer loop head. 1033 }; 1034 1035 PrepareNestedLoopsWhile_While(); 1036 PrepareMIRs(mirs); 1037 PerformSuspendCheckElimination(); 1038 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1039 EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u)); 1040 ASSERT_TRUE(IsBackEdge(7u, 4u)); 1041 EXPECT_FALSE(IsSuspendCheckEdge(7u, 4u)); 1042 } 1043 1044 TEST_F(SuspendCheckEliminationTest, While_While_InvokeInOuterLoopBody) { 1045 static const MIRDef mirs[] = { 1046 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1047 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop. 1048 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1049 DEF_INVOKE(7u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in outer loop body. 1050 DEF_OTHER0(7u, Instruction::GOTO), // Edge back to outer loop head. 1051 }; 1052 1053 PrepareNestedLoopsWhile_While(); 1054 PrepareMIRs(mirs); 1055 PerformSuspendCheckElimination(); 1056 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1057 EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u)); 1058 ASSERT_TRUE(IsBackEdge(7u, 4u)); 1059 EXPECT_FALSE(IsSuspendCheckEdge(7u, 4u)); 1060 } 1061 1062 TEST_F(SuspendCheckEliminationTest, While_While_InvokeInInnerLoopHead) { 1063 static const MIRDef mirs[] = { 1064 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1065 DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in inner loop head. 1066 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop. 1067 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1068 DEF_OTHER0(7u, Instruction::GOTO), // Edge back to outer loop head. 1069 }; 1070 1071 PrepareNestedLoopsWhile_While(); 1072 PrepareMIRs(mirs); 1073 PerformSuspendCheckElimination(); 1074 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1075 EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u)); 1076 ASSERT_TRUE(IsBackEdge(7u, 4u)); 1077 EXPECT_FALSE(IsSuspendCheckEdge(7u, 4u)); 1078 } 1079 1080 TEST_F(SuspendCheckEliminationTest, While_While_InvokeInInnerLoopBody) { 1081 static const MIRDef mirs[] = { 1082 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1083 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop. 1084 DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in inner loop body. 1085 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1086 DEF_OTHER0(7u, Instruction::GOTO), // Edge back to outer loop head. 1087 }; 1088 1089 PrepareNestedLoopsWhile_While(); 1090 PrepareMIRs(mirs); 1091 PerformSuspendCheckElimination(); 1092 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1093 EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u)); 1094 ASSERT_TRUE(IsBackEdge(7u, 4u)); 1095 EXPECT_TRUE(IsSuspendCheckEdge(7u, 4u)); 1096 } 1097 1098 TEST_F(SuspendCheckEliminationTest, While_WhileWhile_InvokeInFirstInnerLoopHead) { 1099 static const MIRDef mirs[] = { 1100 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1101 DEF_INVOKE(5u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in first inner loop head. 1102 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 1. 1103 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1104 DEF_OTHER1(7u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 2. 1105 DEF_OTHER0(8u, Instruction::GOTO), // Edge back to inner loop 2 head. 1106 DEF_OTHER0(9u, Instruction::GOTO), // Edge back to outer loop head. 1107 }; 1108 1109 PrepareNestedLoopsWhile_WhileWhile(); 1110 PrepareMIRs(mirs); 1111 PerformSuspendCheckElimination(); 1112 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1113 EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u)); 1114 ASSERT_TRUE(IsBackEdge(8u, 7u)); 1115 EXPECT_TRUE(IsSuspendCheckEdge(8u, 7u)); 1116 ASSERT_TRUE(IsBackEdge(9u, 4u)); 1117 EXPECT_FALSE(IsSuspendCheckEdge(9u, 4u)); 1118 } 1119 1120 TEST_F(SuspendCheckEliminationTest, While_WhileWhile_InvokeInFirstInnerLoopBody) { 1121 static const MIRDef mirs[] = { 1122 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1123 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 1. 1124 DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in first inner loop body. 1125 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1126 DEF_OTHER1(7u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 2. 1127 DEF_OTHER0(8u, Instruction::GOTO), // Edge back to inner loop 2 head. 1128 DEF_OTHER0(9u, Instruction::GOTO), // Edge back to outer loop head. 1129 }; 1130 1131 PrepareNestedLoopsWhile_WhileWhile(); 1132 PrepareMIRs(mirs); 1133 PerformSuspendCheckElimination(); 1134 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1135 EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u)); 1136 ASSERT_TRUE(IsBackEdge(8u, 7u)); 1137 EXPECT_TRUE(IsSuspendCheckEdge(8u, 7u)); 1138 ASSERT_TRUE(IsBackEdge(9u, 4u)); 1139 EXPECT_TRUE(IsSuspendCheckEdge(9u, 4u)); 1140 } 1141 1142 TEST_F(SuspendCheckEliminationTest, While_WhileWhile_WithExtraEdge_InvokeInFirstInnerLoopBody) { 1143 static const MIRDef mirs[] = { 1144 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1145 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 1. 1146 DEF_INVOKE(6u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in first inner loop body. 1147 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1148 DEF_OTHER1(7u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 2. 1149 DEF_OTHER0(8u, Instruction::GOTO), // Edge back to inner loop 2 head. 1150 DEF_OTHER0(9u, Instruction::GOTO), // Edge back to outer loop head. 1151 }; 1152 1153 PrepareNestedLoopsWhile_WhileWhile_WithExtraEdge(); 1154 PrepareMIRs(mirs); 1155 PerformSuspendCheckElimination(); 1156 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1157 EXPECT_FALSE(IsSuspendCheckEdge(6u, 5u)); 1158 ASSERT_TRUE(IsBackEdge(8u, 7u)); 1159 EXPECT_TRUE(IsSuspendCheckEdge(8u, 7u)); // Unaffected by the extra edge. 1160 ASSERT_TRUE(IsBackEdge(9u, 4u)); 1161 EXPECT_TRUE(IsSuspendCheckEdge(9u, 4u)); 1162 } 1163 1164 TEST_F(SuspendCheckEliminationTest, While_WhileWhile_WithExtraEdge_InvokeInSecondInnerLoopHead) { 1165 static const MIRDef mirs[] = { 1166 DEF_OTHER1(4u, Instruction::IF_NEZ, 1u), // Edge out of outer loop. 1167 DEF_OTHER1(5u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 1. 1168 DEF_OTHER0(6u, Instruction::GOTO), // Edge back to inner loop head. 1169 DEF_INVOKE(7u, Instruction::INVOKE_STATIC, 0u, 0u), // Invoke in second inner loop head. 1170 DEF_OTHER1(7u, Instruction::IF_NEZ, 2u), // Edge out of inner loop 2. 1171 DEF_OTHER0(8u, Instruction::GOTO), // Edge back to inner loop 2 head. 1172 DEF_OTHER0(9u, Instruction::GOTO), // Edge back to outer loop head. 1173 }; 1174 1175 PrepareNestedLoopsWhile_WhileWhile_WithExtraEdge(); 1176 PrepareMIRs(mirs); 1177 PerformSuspendCheckElimination(); 1178 ASSERT_TRUE(IsBackEdge(6u, 5u)); 1179 EXPECT_TRUE(IsSuspendCheckEdge(6u, 5u)); 1180 ASSERT_TRUE(IsBackEdge(8u, 7u)); 1181 EXPECT_FALSE(IsSuspendCheckEdge(8u, 7u)); // Unaffected by the extra edge. 1182 ASSERT_TRUE(IsBackEdge(9u, 4u)); 1183 EXPECT_FALSE(IsSuspendCheckEdge(9u, 4u)); 1184 } 1185 1186 } // namespace art 1187
