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 "compiler_internals.h" 20 #include "dataflow_iterator.h" 21 #include "dataflow_iterator-inl.h" 22 #include "gtest/gtest.h" 23 24 namespace art { 25 26 class ClassInitCheckEliminationTest : public testing::Test { 27 protected: 28 struct SFieldDef { 29 uint16_t field_idx; 30 uintptr_t declaring_dex_file; 31 uint16_t declaring_class_idx; 32 uint16_t declaring_field_idx; 33 }; 34 35 struct BBDef { 36 static constexpr size_t kMaxSuccessors = 4; 37 static constexpr size_t kMaxPredecessors = 4; 38 39 BBType type; 40 size_t num_successors; 41 BasicBlockId successors[kMaxPredecessors]; 42 size_t num_predecessors; 43 BasicBlockId predecessors[kMaxPredecessors]; 44 }; 45 46 struct MIRDef { 47 Instruction::Code opcode; 48 BasicBlockId bbid; 49 uint32_t field_or_method_info; 50 }; 51 52 #define DEF_SUCC0() \ 53 0u, { } 54 #define DEF_SUCC1(s1) \ 55 1u, { s1 } 56 #define DEF_SUCC2(s1, s2) \ 57 2u, { s1, s2 } 58 #define DEF_SUCC3(s1, s2, s3) \ 59 3u, { s1, s2, s3 } 60 #define DEF_SUCC4(s1, s2, s3, s4) \ 61 4u, { s1, s2, s3, s4 } 62 #define DEF_PRED0() \ 63 0u, { } 64 #define DEF_PRED1(p1) \ 65 1u, { p1 } 66 #define DEF_PRED2(p1, p2) \ 67 2u, { p1, p2 } 68 #define DEF_PRED3(p1, p2, p3) \ 69 3u, { p1, p2, p3 } 70 #define DEF_PRED4(p1, p2, p3, p4) \ 71 4u, { p1, p2, p3, p4 } 72 #define DEF_BB(type, succ, pred) \ 73 { type, succ, pred } 74 75 #define DEF_MIR(opcode, bb, field_info) \ 76 { opcode, bb, field_info } 77 78 void DoPrepareSFields(const SFieldDef* defs, size_t count) { 79 cu_.mir_graph->sfield_lowering_infos_.Reset(); 80 cu_.mir_graph->sfield_lowering_infos_.Resize(count); 81 for (size_t i = 0u; i != count; ++i) { 82 const SFieldDef* def = &defs[i]; 83 MirSFieldLoweringInfo field_info(def->field_idx); 84 if (def->declaring_dex_file != 0u) { 85 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 86 field_info.declaring_class_idx_ = def->declaring_class_idx; 87 field_info.declaring_field_idx_ = def->declaring_field_idx; 88 field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic; 89 } 90 ASSERT_EQ(def->declaring_dex_file != 0u, field_info.IsResolved()); 91 ASSERT_FALSE(field_info.IsInitialized()); 92 cu_.mir_graph->sfield_lowering_infos_.Insert(field_info); 93 } 94 } 95 96 template <size_t count> 97 void PrepareSFields(const SFieldDef (&defs)[count]) { 98 DoPrepareSFields(defs, count); 99 } 100 101 void DoPrepareBasicBlocks(const BBDef* defs, size_t count) { 102 cu_.mir_graph->block_id_map_.clear(); 103 cu_.mir_graph->block_list_.Reset(); 104 ASSERT_LT(3u, count); // null, entry, exit and at least one bytecode block. 105 ASSERT_EQ(kNullBlock, defs[0].type); 106 ASSERT_EQ(kEntryBlock, defs[1].type); 107 ASSERT_EQ(kExitBlock, defs[2].type); 108 for (size_t i = 0u; i != count; ++i) { 109 const BBDef* def = &defs[i]; 110 BasicBlock* bb = cu_.mir_graph->NewMemBB(def->type, i); 111 cu_.mir_graph->block_list_.Insert(bb); 112 if (def->num_successors <= 2) { 113 bb->successor_block_list_type = kNotUsed; 114 bb->successor_blocks = nullptr; 115 bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u; 116 bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u; 117 } else { 118 bb->successor_block_list_type = kPackedSwitch; 119 bb->fall_through = 0u; 120 bb->taken = 0u; 121 bb->successor_blocks = new (&cu_.arena) GrowableArray<SuccessorBlockInfo*>( 122 &cu_.arena, def->num_successors, kGrowableArraySuccessorBlocks); 123 for (size_t j = 0u; j != def->num_successors; ++j) { 124 SuccessorBlockInfo* successor_block_info = 125 static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), 126 kArenaAllocSuccessor)); 127 successor_block_info->block = j; 128 successor_block_info->key = 0u; // Not used by class init check elimination. 129 bb->successor_blocks->Insert(successor_block_info); 130 } 131 } 132 bb->predecessors = new (&cu_.arena) GrowableArray<BasicBlockId>( 133 &cu_.arena, def->num_predecessors, kGrowableArrayPredecessors); 134 for (size_t j = 0u; j != def->num_predecessors; ++j) { 135 ASSERT_NE(0u, def->predecessors[j]); 136 bb->predecessors->Insert(def->predecessors[j]); 137 } 138 if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) { 139 bb->data_flow_info = static_cast<BasicBlockDataFlow*>( 140 cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo)); 141 } 142 } 143 cu_.mir_graph->num_blocks_ = count; 144 ASSERT_EQ(count, cu_.mir_graph->block_list_.Size()); 145 cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_.Get(1); 146 ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type); 147 cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_.Get(2); 148 ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type); 149 } 150 151 template <size_t count> 152 void PrepareBasicBlocks(const BBDef (&defs)[count]) { 153 DoPrepareBasicBlocks(defs, count); 154 } 155 156 void DoPrepareMIRs(const MIRDef* defs, size_t count) { 157 mir_count_ = count; 158 mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR)); 159 uint64_t merged_df_flags = 0u; 160 for (size_t i = 0u; i != count; ++i) { 161 const MIRDef* def = &defs[i]; 162 MIR* mir = &mirs_[i]; 163 mir->dalvikInsn.opcode = def->opcode; 164 ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.Size()); 165 BasicBlock* bb = cu_.mir_graph->block_list_.Get(def->bbid); 166 bb->AppendMIR(mir); 167 if (def->opcode >= Instruction::SGET && def->opcode <= Instruction::SPUT_SHORT) { 168 ASSERT_LT(def->field_or_method_info, cu_.mir_graph->sfield_lowering_infos_.Size()); 169 mir->meta.sfield_lowering_info = def->field_or_method_info; 170 } 171 mir->ssa_rep = nullptr; 172 mir->offset = 2 * i; // All insns need to be at least 2 code units long. 173 mir->optimization_flags = 0u; 174 merged_df_flags |= MIRGraph::GetDataFlowAttributes(def->opcode); 175 } 176 cu_.mir_graph->merged_df_flags_ = merged_df_flags; 177 178 code_item_ = static_cast<DexFile::CodeItem*>( 179 cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc)); 180 memset(code_item_, 0, sizeof(DexFile::CodeItem)); 181 code_item_->insns_size_in_code_units_ = 2u * count; 182 cu_.mir_graph->current_code_item_ = cu_.code_item = code_item_; 183 } 184 185 template <size_t count> 186 void PrepareMIRs(const MIRDef (&defs)[count]) { 187 DoPrepareMIRs(defs, count); 188 } 189 190 void PerformClassInitCheckElimination() { 191 cu_.mir_graph->SSATransformationStart(); 192 cu_.mir_graph->ComputeDFSOrders(); 193 cu_.mir_graph->ComputeDominators(); 194 cu_.mir_graph->ComputeTopologicalSortOrder(); 195 cu_.mir_graph->SSATransformationEnd(); 196 bool gate_result = cu_.mir_graph->EliminateClassInitChecksGate(); 197 ASSERT_TRUE(gate_result); 198 LoopRepeatingTopologicalSortIterator iterator(cu_.mir_graph.get()); 199 bool change = false; 200 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) { 201 change = cu_.mir_graph->EliminateClassInitChecks(bb); 202 } 203 cu_.mir_graph->EliminateClassInitChecksEnd(); 204 } 205 206 ClassInitCheckEliminationTest() 207 : pool_(), 208 cu_(&pool_), 209 mir_count_(0u), 210 mirs_(nullptr), 211 code_item_(nullptr) { 212 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena)); 213 } 214 215 ArenaPool pool_; 216 CompilationUnit cu_; 217 size_t mir_count_; 218 MIR* mirs_; 219 DexFile::CodeItem* code_item_; 220 }; 221 222 TEST_F(ClassInitCheckEliminationTest, SingleBlock) { 223 static const SFieldDef sfields[] = { 224 { 0u, 1u, 0u, 0u }, 225 { 1u, 1u, 1u, 1u }, 226 { 2u, 1u, 2u, 2u }, 227 { 3u, 1u, 3u, 3u }, // Same declaring class as sfield[4]. 228 { 4u, 1u, 3u, 4u }, // Same declaring class as sfield[3]. 229 { 5u, 0u, 0u, 0u }, // Unresolved. 230 }; 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(3)), 235 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)), 236 }; 237 static const MIRDef mirs[] = { 238 DEF_MIR(Instruction::SPUT, 3u, 5u), // Unresolved. 239 DEF_MIR(Instruction::SPUT, 3u, 0u), 240 DEF_MIR(Instruction::SGET, 3u, 1u), 241 DEF_MIR(Instruction::SGET, 3u, 2u), 242 DEF_MIR(Instruction::SGET, 3u, 5u), // Unresolved. 243 DEF_MIR(Instruction::SGET, 3u, 0u), 244 DEF_MIR(Instruction::SGET, 3u, 1u), 245 DEF_MIR(Instruction::SGET, 3u, 2u), 246 DEF_MIR(Instruction::SGET, 3u, 5u), // Unresolved. 247 DEF_MIR(Instruction::SGET, 3u, 3u), 248 DEF_MIR(Instruction::SGET, 3u, 4u), 249 }; 250 static const bool expected_ignore_clinit_check[] = { 251 false, false, false, false, true, true, true, true, true, false, true 252 }; 253 254 PrepareSFields(sfields); 255 PrepareBasicBlocks(bbs); 256 PrepareMIRs(mirs); 257 PerformClassInitCheckElimination(); 258 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 259 for (size_t i = 0u; i != arraysize(mirs); ++i) { 260 EXPECT_EQ(expected_ignore_clinit_check[i], 261 (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i; 262 } 263 } 264 265 TEST_F(ClassInitCheckEliminationTest, Diamond) { 266 static const SFieldDef sfields[] = { 267 { 0u, 1u, 0u, 0u }, 268 { 1u, 1u, 1u, 1u }, 269 { 2u, 1u, 2u, 2u }, 270 { 3u, 1u, 3u, 3u }, 271 { 4u, 1u, 4u, 4u }, 272 { 5u, 1u, 5u, 5u }, 273 { 6u, 1u, 6u, 6u }, 274 { 7u, 1u, 7u, 7u }, 275 { 8u, 1u, 8u, 8u }, // Same declaring class as sfield[9]. 276 { 9u, 1u, 8u, 9u }, // Same declaring class as sfield[8]. 277 { 10u, 0u, 0u, 0u }, // Unresolved. 278 }; 279 static const BBDef bbs[] = { 280 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 281 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 282 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 283 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), 284 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), 285 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), 286 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), 287 }; 288 static const MIRDef mirs[] = { 289 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 290 DEF_MIR(Instruction::SGET, 3u, 10u), // Unresolved. 291 DEF_MIR(Instruction::SPUT, 3u, 10u), // Unresolved. 292 DEF_MIR(Instruction::SPUT, 3u, 0u), 293 DEF_MIR(Instruction::SGET, 6u, 0u), // Eliminated (block #3 dominates #6). 294 DEF_MIR(Instruction::SPUT, 4u, 1u), 295 DEF_MIR(Instruction::SGET, 6u, 1u), // Not eliminated (block #4 doesn't dominate #6). 296 DEF_MIR(Instruction::SGET, 3u, 2u), 297 DEF_MIR(Instruction::SGET, 4u, 2u), // Eliminated (block #3 dominates #4). 298 DEF_MIR(Instruction::SGET, 3u, 3u), 299 DEF_MIR(Instruction::SGET, 5u, 3u), // Eliminated (block #3 dominates #5). 300 DEF_MIR(Instruction::SGET, 3u, 4u), 301 DEF_MIR(Instruction::SGET, 6u, 4u), // Eliminated (block #3 dominates #6). 302 DEF_MIR(Instruction::SGET, 4u, 5u), 303 DEF_MIR(Instruction::SGET, 6u, 5u), // Not eliminated (block #4 doesn't dominate #6). 304 DEF_MIR(Instruction::SGET, 5u, 6u), 305 DEF_MIR(Instruction::SGET, 6u, 6u), // Not eliminated (block #5 doesn't dominate #6). 306 DEF_MIR(Instruction::SGET, 4u, 7u), 307 DEF_MIR(Instruction::SGET, 5u, 7u), 308 DEF_MIR(Instruction::SGET, 6u, 7u), // Eliminated (initialized in both blocks #3 and #4). 309 DEF_MIR(Instruction::SGET, 4u, 8u), 310 DEF_MIR(Instruction::SGET, 5u, 9u), 311 DEF_MIR(Instruction::SGET, 6u, 8u), // Eliminated (with sfield[9] in block #5). 312 DEF_MIR(Instruction::SPUT, 6u, 9u), // Eliminated (with sfield[8] in block #4). 313 }; 314 static const bool expected_ignore_clinit_check[] = { 315 false, true, // Unresolved: sfield[10], method[2] 316 false, true, // sfield[0] 317 false, false, // sfield[1] 318 false, true, // sfield[2] 319 false, true, // sfield[3] 320 false, true, // sfield[4] 321 false, false, // sfield[5] 322 false, false, // sfield[6] 323 false, false, true, // sfield[7] 324 false, false, true, true, // sfield[8], sfield[9] 325 }; 326 327 PrepareSFields(sfields); 328 PrepareBasicBlocks(bbs); 329 PrepareMIRs(mirs); 330 PerformClassInitCheckElimination(); 331 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 332 for (size_t i = 0u; i != arraysize(mirs); ++i) { 333 EXPECT_EQ(expected_ignore_clinit_check[i], 334 (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i; 335 } 336 } 337 338 TEST_F(ClassInitCheckEliminationTest, Loop) { 339 static const SFieldDef sfields[] = { 340 { 0u, 1u, 0u, 0u }, 341 { 1u, 1u, 1u, 1u }, 342 }; 343 static const BBDef bbs[] = { 344 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 345 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 346 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 347 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 348 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)), // "taken" loops to self. 349 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 350 }; 351 static const MIRDef mirs[] = { 352 DEF_MIR(Instruction::SGET, 3u, 0u), 353 DEF_MIR(Instruction::SGET, 4u, 1u), 354 DEF_MIR(Instruction::SGET, 5u, 0u), // Eliminated. 355 DEF_MIR(Instruction::SGET, 5u, 1u), // Eliminated. 356 }; 357 static const bool expected_ignore_clinit_check[] = { 358 false, false, true, true 359 }; 360 361 PrepareSFields(sfields); 362 PrepareBasicBlocks(bbs); 363 PrepareMIRs(mirs); 364 PerformClassInitCheckElimination(); 365 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 366 for (size_t i = 0u; i != arraysize(mirs); ++i) { 367 EXPECT_EQ(expected_ignore_clinit_check[i], 368 (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i; 369 } 370 } 371 372 TEST_F(ClassInitCheckEliminationTest, Catch) { 373 static const SFieldDef sfields[] = { 374 { 0u, 1u, 0u, 0u }, 375 { 1u, 1u, 1u, 1u }, 376 { 2u, 1u, 2u, 2u }, 377 { 3u, 1u, 3u, 3u }, 378 }; 379 static const BBDef bbs[] = { 380 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 381 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 382 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 383 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), // The top. 384 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // The throwing insn. 385 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Catch handler. 386 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // The merged block. 387 }; 388 static const MIRDef mirs[] = { 389 DEF_MIR(Instruction::SGET, 3u, 0u), // Before the exception edge. 390 DEF_MIR(Instruction::SGET, 3u, 1u), // Before the exception edge. 391 DEF_MIR(Instruction::SGET, 4u, 2u), // After the exception edge. 392 DEF_MIR(Instruction::SGET, 4u, 3u), // After the exception edge. 393 DEF_MIR(Instruction::SGET, 5u, 0u), // In catch handler; class init check eliminated. 394 DEF_MIR(Instruction::SGET, 5u, 2u), // In catch handler; class init check not eliminated. 395 DEF_MIR(Instruction::SGET, 6u, 0u), // Class init check eliminated. 396 DEF_MIR(Instruction::SGET, 6u, 1u), // Class init check eliminated. 397 DEF_MIR(Instruction::SGET, 6u, 2u), // Class init check eliminated. 398 DEF_MIR(Instruction::SGET, 6u, 3u), // Class init check not eliminated. 399 }; 400 static const bool expected_ignore_clinit_check[] = { 401 false, false, false, false, true, false, true, true, true, false 402 }; 403 404 PrepareSFields(sfields); 405 PrepareBasicBlocks(bbs); 406 BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u); 407 catch_handler->catch_entry = true; 408 // Add successor block info to the check block. 409 BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); 410 check_bb->successor_block_list_type = kCatch; 411 check_bb->successor_blocks = new (&cu_.arena) GrowableArray<SuccessorBlockInfo*>( 412 &cu_.arena, 2, kGrowableArraySuccessorBlocks); 413 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 414 (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 415 successor_block_info->block = catch_handler->id; 416 check_bb->successor_blocks->Insert(successor_block_info); 417 PrepareMIRs(mirs); 418 PerformClassInitCheckElimination(); 419 ASSERT_EQ(arraysize(expected_ignore_clinit_check), mir_count_); 420 for (size_t i = 0u; i != arraysize(mirs); ++i) { 421 EXPECT_EQ(expected_ignore_clinit_check[i], 422 (mirs_[i].optimization_flags & MIR_IGNORE_CLINIT_CHECK) != 0) << i; 423 } 424 } 425 426 } // namespace art 427
