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 "base/logging.h" 18 #include "dataflow_iterator-inl.h" 19 #include "dex/mir_field_info.h" 20 #include "global_value_numbering.h" 21 #include "local_value_numbering.h" 22 #include "gtest/gtest.h" 23 24 namespace art { 25 26 class GlobalValueNumberingTest : public testing::Test { 27 protected: 28 static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue; 29 30 struct IFieldDef { 31 uint16_t field_idx; 32 uintptr_t declaring_dex_file; 33 uint16_t declaring_field_idx; 34 bool is_volatile; 35 DexMemAccessType type; 36 }; 37 38 struct SFieldDef { 39 uint16_t field_idx; 40 uintptr_t declaring_dex_file; 41 uint16_t declaring_field_idx; 42 bool is_volatile; 43 DexMemAccessType type; 44 }; 45 46 struct BBDef { 47 static constexpr size_t kMaxSuccessors = 4; 48 static constexpr size_t kMaxPredecessors = 4; 49 50 BBType type; 51 size_t num_successors; 52 BasicBlockId successors[kMaxPredecessors]; 53 size_t num_predecessors; 54 BasicBlockId predecessors[kMaxPredecessors]; 55 }; 56 57 struct MIRDef { 58 static constexpr size_t kMaxSsaDefs = 2; 59 static constexpr size_t kMaxSsaUses = 4; 60 61 BasicBlockId bbid; 62 Instruction::Code opcode; 63 int64_t value; 64 uint32_t field_info; 65 size_t num_uses; 66 int32_t uses[kMaxSsaUses]; 67 size_t num_defs; 68 int32_t defs[kMaxSsaDefs]; 69 }; 70 71 #define DEF_SUCC0() \ 72 0u, { } 73 #define DEF_SUCC1(s1) \ 74 1u, { s1 } 75 #define DEF_SUCC2(s1, s2) \ 76 2u, { s1, s2 } 77 #define DEF_SUCC3(s1, s2, s3) \ 78 3u, { s1, s2, s3 } 79 #define DEF_SUCC4(s1, s2, s3, s4) \ 80 4u, { s1, s2, s3, s4 } 81 #define DEF_PRED0() \ 82 0u, { } 83 #define DEF_PRED1(p1) \ 84 1u, { p1 } 85 #define DEF_PRED2(p1, p2) \ 86 2u, { p1, p2 } 87 #define DEF_PRED3(p1, p2, p3) \ 88 3u, { p1, p2, p3 } 89 #define DEF_PRED4(p1, p2, p3, p4) \ 90 4u, { p1, p2, p3, p4 } 91 #define DEF_BB(type, succ, pred) \ 92 { type, succ, pred } 93 94 #define DEF_CONST(bb, opcode, reg, value) \ 95 { bb, opcode, value, 0u, 0, { }, 1, { reg } } 96 #define DEF_CONST_WIDE(bb, opcode, reg, value) \ 97 { bb, opcode, value, 0u, 0, { }, 2, { reg, reg + 1 } } 98 #define DEF_CONST_STRING(bb, opcode, reg, index) \ 99 { bb, opcode, index, 0u, 0, { }, 1, { reg } } 100 #define DEF_IGET(bb, opcode, reg, obj, field_info) \ 101 { bb, opcode, 0u, field_info, 1, { obj }, 1, { reg } } 102 #define DEF_IGET_WIDE(bb, opcode, reg, obj, field_info) \ 103 { bb, opcode, 0u, field_info, 1, { obj }, 2, { reg, reg + 1 } } 104 #define DEF_IPUT(bb, opcode, reg, obj, field_info) \ 105 { bb, opcode, 0u, field_info, 2, { reg, obj }, 0, { } } 106 #define DEF_IPUT_WIDE(bb, opcode, reg, obj, field_info) \ 107 { bb, opcode, 0u, field_info, 3, { reg, reg + 1, obj }, 0, { } } 108 #define DEF_SGET(bb, opcode, reg, field_info) \ 109 { bb, opcode, 0u, field_info, 0, { }, 1, { reg } } 110 #define DEF_SGET_WIDE(bb, opcode, reg, field_info) \ 111 { bb, opcode, 0u, field_info, 0, { }, 2, { reg, reg + 1 } } 112 #define DEF_SPUT(bb, opcode, reg, field_info) \ 113 { bb, opcode, 0u, field_info, 1, { reg }, 0, { } } 114 #define DEF_SPUT_WIDE(bb, opcode, reg, field_info) \ 115 { bb, opcode, 0u, field_info, 2, { reg, reg + 1 }, 0, { } } 116 #define DEF_AGET(bb, opcode, reg, obj, idx) \ 117 { bb, opcode, 0u, 0u, 2, { obj, idx }, 1, { reg } } 118 #define DEF_AGET_WIDE(bb, opcode, reg, obj, idx) \ 119 { bb, opcode, 0u, 0u, 2, { obj, idx }, 2, { reg, reg + 1 } } 120 #define DEF_APUT(bb, opcode, reg, obj, idx) \ 121 { bb, opcode, 0u, 0u, 3, { reg, obj, idx }, 0, { } } 122 #define DEF_APUT_WIDE(bb, opcode, reg, obj, idx) \ 123 { bb, opcode, 0u, 0u, 4, { reg, reg + 1, obj, idx }, 0, { } } 124 #define DEF_INVOKE1(bb, opcode, reg) \ 125 { bb, opcode, 0u, 0u, 1, { reg }, 0, { } } 126 #define DEF_UNIQUE_REF(bb, opcode, reg) \ 127 { bb, opcode, 0u, 0u, 0, { }, 1, { reg } } // CONST_CLASS, CONST_STRING, NEW_ARRAY, ... 128 #define DEF_IFZ(bb, opcode, reg) \ 129 { bb, opcode, 0u, 0u, 1, { reg }, 0, { } } 130 #define DEF_MOVE(bb, opcode, reg, src) \ 131 { bb, opcode, 0u, 0u, 1, { src }, 1, { reg } } 132 #define DEF_MOVE_WIDE(bb, opcode, reg, src) \ 133 { bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } } 134 #define DEF_PHI2(bb, reg, src1, src2) \ 135 { bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } } 136 #define DEF_BINOP(bb, opcode, result, src1, src2) \ 137 { bb, opcode, 0u, 0u, 2, { src1, src2 }, 1, { result } } 138 #define DEF_UNOP(bb, opcode, result, src) DEF_MOVE(bb, opcode, result, src) 139 140 void DoPrepareIFields(const IFieldDef* defs, size_t count) { 141 cu_.mir_graph->ifield_lowering_infos_.clear(); 142 cu_.mir_graph->ifield_lowering_infos_.reserve(count); 143 for (size_t i = 0u; i != count; ++i) { 144 const IFieldDef* def = &defs[i]; 145 MirIFieldLoweringInfo field_info(def->field_idx, def->type, false); 146 if (def->declaring_dex_file != 0u) { 147 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 148 field_info.declaring_field_idx_ = def->declaring_field_idx; 149 field_info.flags_ &= ~(def->is_volatile ? 0u : MirSFieldLoweringInfo::kFlagIsVolatile); 150 } 151 cu_.mir_graph->ifield_lowering_infos_.push_back(field_info); 152 } 153 } 154 155 template <size_t count> 156 void PrepareIFields(const IFieldDef (&defs)[count]) { 157 DoPrepareIFields(defs, count); 158 } 159 160 void DoPrepareSFields(const SFieldDef* defs, size_t count) { 161 cu_.mir_graph->sfield_lowering_infos_.clear(); 162 cu_.mir_graph->sfield_lowering_infos_.reserve(count); 163 for (size_t i = 0u; i != count; ++i) { 164 const SFieldDef* def = &defs[i]; 165 MirSFieldLoweringInfo field_info(def->field_idx, def->type); 166 // Mark even unresolved fields as initialized. 167 field_info.flags_ |= MirSFieldLoweringInfo::kFlagClassIsInitialized; 168 // NOTE: MirSFieldLoweringInfo::kFlagClassIsInDexCache isn't used by GVN. 169 if (def->declaring_dex_file != 0u) { 170 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 171 field_info.declaring_field_idx_ = def->declaring_field_idx; 172 field_info.flags_ &= ~(def->is_volatile ? 0u : MirSFieldLoweringInfo::kFlagIsVolatile); 173 } 174 cu_.mir_graph->sfield_lowering_infos_.push_back(field_info); 175 } 176 } 177 178 template <size_t count> 179 void PrepareSFields(const SFieldDef (&defs)[count]) { 180 DoPrepareSFields(defs, count); 181 } 182 183 void DoPrepareBasicBlocks(const BBDef* defs, size_t count) { 184 cu_.mir_graph->block_id_map_.clear(); 185 cu_.mir_graph->block_list_.clear(); 186 ASSERT_LT(3u, count); // null, entry, exit and at least one bytecode block. 187 ASSERT_EQ(kNullBlock, defs[0].type); 188 ASSERT_EQ(kEntryBlock, defs[1].type); 189 ASSERT_EQ(kExitBlock, defs[2].type); 190 for (size_t i = 0u; i != count; ++i) { 191 const BBDef* def = &defs[i]; 192 BasicBlock* bb = cu_.mir_graph->CreateNewBB(def->type); 193 if (def->num_successors <= 2) { 194 bb->successor_block_list_type = kNotUsed; 195 bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u; 196 bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u; 197 } else { 198 bb->successor_block_list_type = kPackedSwitch; 199 bb->fall_through = 0u; 200 bb->taken = 0u; 201 bb->successor_blocks.reserve(def->num_successors); 202 for (size_t j = 0u; j != def->num_successors; ++j) { 203 SuccessorBlockInfo* successor_block_info = 204 static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), 205 kArenaAllocSuccessor)); 206 successor_block_info->block = j; 207 successor_block_info->key = 0u; // Not used by class init check elimination. 208 bb->successor_blocks.push_back(successor_block_info); 209 } 210 } 211 bb->predecessors.assign(def->predecessors, def->predecessors + def->num_predecessors); 212 if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) { 213 bb->data_flow_info = static_cast<BasicBlockDataFlow*>( 214 cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo)); 215 bb->data_flow_info->live_in_v = live_in_v_; 216 } 217 } 218 ASSERT_EQ(count, cu_.mir_graph->block_list_.size()); 219 cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_[1]; 220 ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type); 221 cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_[2]; 222 ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type); 223 } 224 225 template <size_t count> 226 void PrepareBasicBlocks(const BBDef (&defs)[count]) { 227 DoPrepareBasicBlocks(defs, count); 228 } 229 230 void DoPrepareMIRs(const MIRDef* defs, size_t count) { 231 mir_count_ = count; 232 mirs_ = cu_.arena.AllocArray<MIR>(count, kArenaAllocMIR); 233 ssa_reps_.resize(count); 234 for (size_t i = 0u; i != count; ++i) { 235 const MIRDef* def = &defs[i]; 236 MIR* mir = &mirs_[i]; 237 ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.size()); 238 BasicBlock* bb = cu_.mir_graph->block_list_[def->bbid]; 239 bb->AppendMIR(mir); 240 mir->dalvikInsn.opcode = def->opcode; 241 mir->dalvikInsn.vB = static_cast<int32_t>(def->value); 242 mir->dalvikInsn.vB_wide = def->value; 243 if (IsInstructionIGetOrIPut(def->opcode)) { 244 ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.size()); 245 mir->meta.ifield_lowering_info = def->field_info; 246 ASSERT_EQ(cu_.mir_graph->ifield_lowering_infos_[def->field_info].MemAccessType(), 247 IGetOrIPutMemAccessType(def->opcode)); 248 } else if (IsInstructionSGetOrSPut(def->opcode)) { 249 ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.size()); 250 mir->meta.sfield_lowering_info = def->field_info; 251 ASSERT_EQ(cu_.mir_graph->sfield_lowering_infos_[def->field_info].MemAccessType(), 252 SGetOrSPutMemAccessType(def->opcode)); 253 } else if (def->opcode == static_cast<Instruction::Code>(kMirOpPhi)) { 254 mir->meta.phi_incoming = 255 allocator_->AllocArray<BasicBlockId>(def->num_uses, kArenaAllocDFInfo); 256 ASSERT_EQ(def->num_uses, bb->predecessors.size()); 257 std::copy(bb->predecessors.begin(), bb->predecessors.end(), mir->meta.phi_incoming); 258 } 259 mir->ssa_rep = &ssa_reps_[i]; 260 mir->ssa_rep->num_uses = def->num_uses; 261 mir->ssa_rep->uses = const_cast<int32_t*>(def->uses); // Not modified by LVN. 262 mir->ssa_rep->num_defs = def->num_defs; 263 mir->ssa_rep->defs = const_cast<int32_t*>(def->defs); // Not modified by LVN. 264 mir->dalvikInsn.opcode = def->opcode; 265 mir->offset = i; // LVN uses offset only for debug output 266 mir->optimization_flags = 0u; 267 } 268 DexFile::CodeItem* code_item = static_cast<DexFile::CodeItem*>( 269 cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc)); 270 code_item->insns_size_in_code_units_ = 2u * count; 271 cu_.mir_graph->current_code_item_ = code_item; 272 } 273 274 template <size_t count> 275 void PrepareMIRs(const MIRDef (&defs)[count]) { 276 DoPrepareMIRs(defs, count); 277 } 278 279 void DoPrepareVregToSsaMapExit(BasicBlockId bb_id, const int32_t* map, size_t count) { 280 BasicBlock* bb = cu_.mir_graph->GetBasicBlock(bb_id); 281 ASSERT_TRUE(bb != nullptr); 282 ASSERT_TRUE(bb->data_flow_info != nullptr); 283 bb->data_flow_info->vreg_to_ssa_map_exit = 284 cu_.arena.AllocArray<int32_t>(count, kArenaAllocDFInfo); 285 std::copy_n(map, count, bb->data_flow_info->vreg_to_ssa_map_exit); 286 } 287 288 template <size_t count> 289 void PrepareVregToSsaMapExit(BasicBlockId bb_id, const int32_t (&map)[count]) { 290 DoPrepareVregToSsaMapExit(bb_id, map, count); 291 } 292 293 template <size_t count> 294 void MarkAsWideSRegs(const int32_t (&sregs)[count]) { 295 for (int32_t sreg : sregs) { 296 cu_.mir_graph->reg_location_[sreg].wide = true; 297 cu_.mir_graph->reg_location_[sreg + 1].wide = true; 298 cu_.mir_graph->reg_location_[sreg + 1].high_word = true; 299 } 300 } 301 302 void PerformGVN() { 303 DoPerformGVN<LoopRepeatingTopologicalSortIterator>(); 304 } 305 306 void PerformPreOrderDfsGVN() { 307 DoPerformGVN<RepeatingPreOrderDfsIterator>(); 308 } 309 310 template <typename IteratorType> 311 void DoPerformGVN() { 312 cu_.mir_graph->SSATransformationStart(); 313 cu_.mir_graph->ComputeDFSOrders(); 314 cu_.mir_graph->ComputeDominators(); 315 cu_.mir_graph->ComputeTopologicalSortOrder(); 316 cu_.mir_graph->SSATransformationEnd(); 317 cu_.mir_graph->temp_.gvn.ifield_ids = GlobalValueNumbering::PrepareGvnFieldIds( 318 allocator_.get(), cu_.mir_graph->ifield_lowering_infos_); 319 cu_.mir_graph->temp_.gvn.sfield_ids = GlobalValueNumbering::PrepareGvnFieldIds( 320 allocator_.get(), cu_.mir_graph->sfield_lowering_infos_); 321 ASSERT_TRUE(gvn_ == nullptr); 322 gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get(), 323 GlobalValueNumbering::kModeGvn)); 324 value_names_.resize(mir_count_, 0xffffu); 325 IteratorType iterator(cu_.mir_graph.get()); 326 bool change = false; 327 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) { 328 LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb); 329 if (lvn != nullptr) { 330 for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) { 331 value_names_[mir - mirs_] = lvn->GetValueNumber(mir); 332 } 333 } 334 change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb); 335 ASSERT_TRUE(gvn_->Good()); 336 } 337 } 338 339 void PerformGVNCodeModifications() { 340 ASSERT_TRUE(gvn_ != nullptr); 341 ASSERT_TRUE(gvn_->Good()); 342 gvn_->StartPostProcessing(); 343 TopologicalSortIterator iterator(cu_.mir_graph.get()); 344 for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { 345 LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb); 346 if (lvn != nullptr) { 347 for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) { 348 uint16_t value_name = lvn->GetValueNumber(mir); 349 ASSERT_EQ(value_name, value_names_[mir - mirs_]); 350 } 351 } 352 bool change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb); 353 ASSERT_FALSE(change); 354 ASSERT_TRUE(gvn_->Good()); 355 } 356 } 357 358 GlobalValueNumberingTest() 359 : pool_(), 360 cu_(&pool_, kRuntimeISA, nullptr, nullptr), 361 mir_count_(0u), 362 mirs_(nullptr), 363 ssa_reps_(), 364 allocator_(), 365 gvn_(), 366 value_names_(), 367 live_in_v_(new (&cu_.arena) ArenaBitVector(&cu_.arena, kMaxSsaRegs, false, kBitMapMisc)) { 368 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena)); 369 cu_.access_flags = kAccStatic; // Don't let "this" interfere with this test. 370 allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack)); 371 // By default, the zero-initialized reg_location_[.] with ref == false tells LVN that 372 // 0 constants are integral, not references, and the values are all narrow. 373 // Nothing else is used by LVN/GVN. Tests can override the default values as needed. 374 cu_.mir_graph->reg_location_ = 375 cu_.arena.AllocArray<RegLocation>(kMaxSsaRegs, kArenaAllocRegAlloc); 376 cu_.mir_graph->num_ssa_regs_ = kMaxSsaRegs; 377 // Bind all possible sregs to live vregs for test purposes. 378 live_in_v_->SetInitialBits(kMaxSsaRegs); 379 cu_.mir_graph->ssa_base_vregs_.reserve(kMaxSsaRegs); 380 cu_.mir_graph->ssa_subscripts_.reserve(kMaxSsaRegs); 381 for (unsigned int i = 0; i < kMaxSsaRegs; i++) { 382 cu_.mir_graph->ssa_base_vregs_.push_back(i); 383 cu_.mir_graph->ssa_subscripts_.push_back(0); 384 } 385 // Set shorty for a void-returning method without arguments. 386 cu_.shorty = "V"; 387 } 388 389 static constexpr size_t kMaxSsaRegs = 16384u; 390 391 ArenaPool pool_; 392 CompilationUnit cu_; 393 size_t mir_count_; 394 MIR* mirs_; 395 std::vector<SSARepresentation> ssa_reps_; 396 std::unique_ptr<ScopedArenaAllocator> allocator_; 397 std::unique_ptr<GlobalValueNumbering> gvn_; 398 std::vector<uint16_t> value_names_; 399 ArenaBitVector* live_in_v_; 400 }; 401 402 constexpr uint16_t GlobalValueNumberingTest::kNoValue; 403 404 class GlobalValueNumberingTestDiamond : public GlobalValueNumberingTest { 405 public: 406 GlobalValueNumberingTestDiamond(); 407 408 private: 409 static const BBDef kDiamondBbs[]; 410 }; 411 412 const GlobalValueNumberingTest::BBDef GlobalValueNumberingTestDiamond::kDiamondBbs[] = { 413 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 414 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 415 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 416 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // Block #3, top of the diamond. 417 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #4, left side. 418 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #5, right side. 419 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // Block #6, bottom. 420 }; 421 422 GlobalValueNumberingTestDiamond::GlobalValueNumberingTestDiamond() 423 : GlobalValueNumberingTest() { 424 PrepareBasicBlocks(kDiamondBbs); 425 } 426 427 class GlobalValueNumberingTestLoop : public GlobalValueNumberingTest { 428 public: 429 GlobalValueNumberingTestLoop(); 430 431 private: 432 static const BBDef kLoopBbs[]; 433 }; 434 435 const GlobalValueNumberingTest::BBDef GlobalValueNumberingTestLoop::kLoopBbs[] = { 436 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 437 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 438 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 439 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 440 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)), // "taken" loops to self. 441 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 442 }; 443 444 GlobalValueNumberingTestLoop::GlobalValueNumberingTestLoop() 445 : GlobalValueNumberingTest() { 446 PrepareBasicBlocks(kLoopBbs); 447 } 448 449 class GlobalValueNumberingTestCatch : public GlobalValueNumberingTest { 450 public: 451 GlobalValueNumberingTestCatch(); 452 453 private: 454 static const BBDef kCatchBbs[]; 455 }; 456 457 const GlobalValueNumberingTest::BBDef GlobalValueNumberingTestCatch::kCatchBbs[] = { 458 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 459 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 460 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 461 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), // The top. 462 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // The throwing insn. 463 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Catch handler. 464 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // The merged block. 465 }; 466 467 GlobalValueNumberingTestCatch::GlobalValueNumberingTestCatch() 468 : GlobalValueNumberingTest() { 469 PrepareBasicBlocks(kCatchBbs); 470 // Mark catch handler. 471 BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u); 472 catch_handler->catch_entry = true; 473 // Add successor block info to the check block. 474 BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); 475 check_bb->successor_block_list_type = kCatch; 476 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 477 (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 478 successor_block_info->block = catch_handler->id; 479 check_bb->successor_blocks.push_back(successor_block_info); 480 } 481 482 class GlobalValueNumberingTestTwoConsecutiveLoops : public GlobalValueNumberingTest { 483 public: 484 GlobalValueNumberingTestTwoConsecutiveLoops(); 485 486 private: 487 static const BBDef kTwoConsecutiveLoopsBbs[]; 488 }; 489 490 const GlobalValueNumberingTest::BBDef 491 GlobalValueNumberingTestTwoConsecutiveLoops::kTwoConsecutiveLoopsBbs[] = { 492 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 493 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 494 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(9)), 495 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 496 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 6), DEF_PRED2(3, 5)), // "taken" skips over the loop. 497 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(4)), 498 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(4)), 499 DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED2(6, 8)), // "taken" skips over the loop. 500 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(7)), 501 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(7)), 502 }; 503 504 GlobalValueNumberingTestTwoConsecutiveLoops::GlobalValueNumberingTestTwoConsecutiveLoops() 505 : GlobalValueNumberingTest() { 506 PrepareBasicBlocks(kTwoConsecutiveLoopsBbs); 507 } 508 509 class GlobalValueNumberingTestTwoNestedLoops : public GlobalValueNumberingTest { 510 public: 511 GlobalValueNumberingTestTwoNestedLoops(); 512 513 private: 514 static const BBDef kTwoNestedLoopsBbs[]; 515 }; 516 517 const GlobalValueNumberingTest::BBDef 518 GlobalValueNumberingTestTwoNestedLoops::kTwoNestedLoopsBbs[] = { 519 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 520 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 521 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(8)), 522 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 523 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 8), DEF_PRED2(3, 7)), // "taken" skips over the loop. 524 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)), // "taken" skips over the loop. 525 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)), 526 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(5)), 527 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 528 }; 529 530 GlobalValueNumberingTestTwoNestedLoops::GlobalValueNumberingTestTwoNestedLoops() 531 : GlobalValueNumberingTest() { 532 PrepareBasicBlocks(kTwoNestedLoopsBbs); 533 } 534 535 TEST_F(GlobalValueNumberingTestDiamond, NonAliasingIFields) { 536 static const IFieldDef ifields[] = { 537 { 0u, 1u, 0u, false, kDexMemAccessWord }, 538 { 1u, 1u, 1u, false, kDexMemAccessWord }, 539 { 2u, 1u, 2u, false, kDexMemAccessWord }, 540 { 3u, 1u, 3u, false, kDexMemAccessWord }, 541 { 4u, 1u, 4u, false, kDexMemAccessShort }, 542 { 5u, 1u, 5u, false, kDexMemAccessChar }, 543 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 544 { 7u, 1u, 7u, false, kDexMemAccessWord }, 545 { 8u, 0u, 0u, false, kDexMemAccessWord }, // Unresolved. 546 { 9u, 1u, 9u, false, kDexMemAccessWord }, 547 { 10u, 1u, 10u, false, kDexMemAccessWord }, 548 { 11u, 1u, 11u, false, kDexMemAccessWord }, 549 }; 550 static const MIRDef mirs[] = { 551 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 552 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 100u), 553 DEF_IGET(3, Instruction::IGET, 1u, 100u, 0u), 554 DEF_IGET(6, Instruction::IGET, 2u, 100u, 0u), // Same as at the top. 555 556 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 200u), 557 DEF_IGET(4, Instruction::IGET, 4u, 200u, 1u), 558 DEF_IGET(6, Instruction::IGET, 5u, 200u, 1u), // Same as at the left side. 559 560 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 300u), 561 DEF_IGET(3, Instruction::IGET, 7u, 300u, 2u), 562 DEF_CONST(5, Instruction::CONST, 8u, 1000), 563 DEF_IPUT(5, Instruction::IPUT, 8u, 300u, 2u), 564 DEF_IGET(6, Instruction::IGET, 10u, 300u, 2u), // Differs from the top and the CONST. 565 566 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 400u), 567 DEF_IGET(3, Instruction::IGET, 12u, 400u, 3u), 568 DEF_CONST(3, Instruction::CONST, 13u, 2000), 569 DEF_IPUT(4, Instruction::IPUT, 13u, 400u, 3u), 570 DEF_IPUT(5, Instruction::IPUT, 13u, 400u, 3u), 571 DEF_IGET(6, Instruction::IGET, 16u, 400u, 3u), // Differs from the top, equals the CONST. 572 573 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 500u), 574 DEF_IGET(3, Instruction::IGET_SHORT, 18u, 500u, 4u), 575 DEF_IGET(3, Instruction::IGET_CHAR, 19u, 500u, 5u), 576 DEF_IPUT(4, Instruction::IPUT_SHORT, 20u, 500u, 6u), // Clobbers field #4, not #5. 577 DEF_IGET(6, Instruction::IGET_SHORT, 21u, 500u, 4u), // Differs from the top. 578 DEF_IGET(6, Instruction::IGET_CHAR, 22u, 500u, 5u), // Same as the top. 579 580 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 600u), 581 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 601u), 582 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 602u), 583 DEF_IGET(3, Instruction::IGET, 26u, 600u, 7u), 584 DEF_IGET(3, Instruction::IGET, 27u, 601u, 7u), 585 DEF_IPUT(4, Instruction::IPUT, 28u, 602u, 8u), // Doesn't clobber field #7 for other refs. 586 DEF_IGET(6, Instruction::IGET, 29u, 600u, 7u), // Same as the top. 587 DEF_IGET(6, Instruction::IGET, 30u, 601u, 7u), // Same as the top. 588 589 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 700u), 590 DEF_CONST(4, Instruction::CONST, 32u, 3000), 591 DEF_IPUT(4, Instruction::IPUT, 32u, 700u, 9u), 592 DEF_IPUT(4, Instruction::IPUT, 32u, 700u, 10u), 593 DEF_CONST(5, Instruction::CONST, 35u, 3001), 594 DEF_IPUT(5, Instruction::IPUT, 35u, 700u, 9u), 595 DEF_IPUT(5, Instruction::IPUT, 35u, 700u, 10u), 596 DEF_IGET(6, Instruction::IGET, 38u, 700u, 9u), 597 DEF_IGET(6, Instruction::IGET, 39u, 700u, 10u), // Same value as read from field #9. 598 599 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 800u), 600 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 801u), 601 DEF_CONST(4, Instruction::CONST, 42u, 3000), 602 DEF_IPUT(4, Instruction::IPUT, 42u, 800u, 11u), 603 DEF_IPUT(4, Instruction::IPUT, 42u, 801u, 11u), 604 DEF_CONST(5, Instruction::CONST, 45u, 3001), 605 DEF_IPUT(5, Instruction::IPUT, 45u, 800u, 11u), 606 DEF_IPUT(5, Instruction::IPUT, 45u, 801u, 11u), 607 DEF_IGET(6, Instruction::IGET, 48u, 800u, 11u), 608 DEF_IGET(6, Instruction::IGET, 49u, 801u, 11u), // Same value as read from ref 46u. 609 610 // Invoke doesn't interfere with non-aliasing refs. There's one test above where a reference 611 // escapes in the left BB (we let a reference escape if we use it to store to an unresolved 612 // field) and the INVOKE in the right BB shouldn't interfere with that either. 613 DEF_INVOKE1(5, Instruction::INVOKE_STATIC, 48u), 614 }; 615 616 PrepareIFields(ifields); 617 PrepareMIRs(mirs); 618 PerformGVN(); 619 ASSERT_EQ(arraysize(mirs), value_names_.size()); 620 EXPECT_EQ(value_names_[1], value_names_[2]); 621 622 EXPECT_EQ(value_names_[4], value_names_[5]); 623 624 EXPECT_NE(value_names_[7], value_names_[10]); 625 EXPECT_NE(value_names_[8], value_names_[10]); 626 627 EXPECT_NE(value_names_[12], value_names_[16]); 628 EXPECT_EQ(value_names_[13], value_names_[16]); 629 630 EXPECT_NE(value_names_[18], value_names_[21]); 631 EXPECT_EQ(value_names_[19], value_names_[22]); 632 633 EXPECT_EQ(value_names_[26], value_names_[29]); 634 EXPECT_EQ(value_names_[27], value_names_[30]); 635 636 EXPECT_EQ(value_names_[38], value_names_[39]); 637 638 EXPECT_EQ(value_names_[48], value_names_[49]); 639 } 640 641 TEST_F(GlobalValueNumberingTestDiamond, AliasingIFieldsSingleObject) { 642 static const IFieldDef ifields[] = { 643 { 0u, 1u, 0u, false, kDexMemAccessWord }, 644 { 1u, 1u, 1u, false, kDexMemAccessWord }, 645 { 2u, 1u, 2u, false, kDexMemAccessWord }, 646 { 3u, 1u, 3u, false, kDexMemAccessWord }, 647 { 4u, 1u, 4u, false, kDexMemAccessShort }, 648 { 5u, 1u, 5u, false, kDexMemAccessChar }, 649 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 650 { 7u, 1u, 7u, false, kDexMemAccessWord }, 651 { 8u, 1u, 8u, false, kDexMemAccessWord }, 652 }; 653 static const MIRDef mirs[] = { 654 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 655 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u), 656 DEF_IGET(6, Instruction::IGET, 1u, 100u, 0u), // Same as at the top. 657 658 DEF_IGET(4, Instruction::IGET, 2u, 100u, 1u), 659 DEF_IGET(6, Instruction::IGET, 3u, 100u, 1u), // Same as at the left side. 660 661 DEF_IGET(3, Instruction::IGET, 4u, 100u, 2u), 662 DEF_CONST(5, Instruction::CONST, 5u, 1000), 663 DEF_IPUT(5, Instruction::IPUT, 5u, 100u, 2u), 664 DEF_IGET(6, Instruction::IGET, 7u, 100u, 2u), // Differs from the top and the CONST. 665 666 DEF_IGET(3, Instruction::IGET, 8u, 100u, 3u), 667 DEF_CONST(3, Instruction::CONST, 9u, 2000), 668 DEF_IPUT(4, Instruction::IPUT, 9u, 100u, 3u), 669 DEF_IPUT(5, Instruction::IPUT, 9u, 100u, 3u), 670 DEF_IGET(6, Instruction::IGET, 12u, 100u, 3u), // Differs from the top, equals the CONST. 671 672 DEF_IGET(3, Instruction::IGET_SHORT, 13u, 100u, 4u), 673 DEF_IGET(3, Instruction::IGET_CHAR, 14u, 100u, 5u), 674 DEF_IPUT(4, Instruction::IPUT_SHORT, 15u, 100u, 6u), // Clobbers field #4, not #5. 675 DEF_IGET(6, Instruction::IGET_SHORT, 16u, 100u, 4u), // Differs from the top. 676 DEF_IGET(6, Instruction::IGET_CHAR, 17u, 100u, 5u), // Same as the top. 677 678 DEF_CONST(4, Instruction::CONST, 18u, 3000), 679 DEF_IPUT(4, Instruction::IPUT, 18u, 100u, 7u), 680 DEF_IPUT(4, Instruction::IPUT, 18u, 100u, 8u), 681 DEF_CONST(5, Instruction::CONST, 21u, 3001), 682 DEF_IPUT(5, Instruction::IPUT, 21u, 100u, 7u), 683 DEF_IPUT(5, Instruction::IPUT, 21u, 100u, 8u), 684 DEF_IGET(6, Instruction::IGET, 24u, 100u, 7u), 685 DEF_IGET(6, Instruction::IGET, 25u, 100u, 8u), // Same value as read from field #7. 686 }; 687 688 PrepareIFields(ifields); 689 PrepareMIRs(mirs); 690 PerformGVN(); 691 ASSERT_EQ(arraysize(mirs), value_names_.size()); 692 EXPECT_EQ(value_names_[0], value_names_[1]); 693 694 EXPECT_EQ(value_names_[2], value_names_[3]); 695 696 EXPECT_NE(value_names_[4], value_names_[7]); 697 EXPECT_NE(value_names_[5], value_names_[7]); 698 699 EXPECT_NE(value_names_[8], value_names_[12]); 700 EXPECT_EQ(value_names_[9], value_names_[12]); 701 702 EXPECT_NE(value_names_[13], value_names_[16]); 703 EXPECT_EQ(value_names_[14], value_names_[17]); 704 705 EXPECT_EQ(value_names_[24], value_names_[25]); 706 } 707 708 TEST_F(GlobalValueNumberingTestDiamond, AliasingIFieldsTwoObjects) { 709 static const IFieldDef ifields[] = { 710 { 0u, 1u, 0u, false, kDexMemAccessWord }, 711 { 1u, 1u, 1u, false, kDexMemAccessWord }, 712 { 2u, 1u, 2u, false, kDexMemAccessWord }, 713 { 3u, 1u, 3u, false, kDexMemAccessWord }, 714 { 4u, 1u, 4u, false, kDexMemAccessShort }, 715 { 5u, 1u, 5u, false, kDexMemAccessChar }, 716 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 717 { 7u, 1u, 7u, false, kDexMemAccessWord }, 718 { 8u, 1u, 8u, false, kDexMemAccessWord }, 719 }; 720 static const MIRDef mirs[] = { 721 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 722 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u), 723 DEF_IPUT(4, Instruction::IPUT, 1u, 101u, 0u), // May alias with the IGET at the top. 724 DEF_IGET(6, Instruction::IGET, 2u, 100u, 0u), // Differs from the top. 725 726 DEF_IGET(3, Instruction::IGET, 3u, 100u, 1u), 727 DEF_IPUT(5, Instruction::IPUT, 3u, 101u, 1u), // If aliasing, stores the same value. 728 DEF_IGET(6, Instruction::IGET, 5u, 100u, 1u), // Same as the top. 729 730 DEF_IGET(3, Instruction::IGET, 6u, 100u, 2u), 731 DEF_CONST(5, Instruction::CONST, 7u, 1000), 732 DEF_IPUT(5, Instruction::IPUT, 7u, 101u, 2u), 733 DEF_IGET(6, Instruction::IGET, 9u, 100u, 2u), // Differs from the top and the CONST. 734 735 DEF_IGET(3, Instruction::IGET, 10u, 100u, 3u), 736 DEF_CONST(3, Instruction::CONST, 11u, 2000), 737 DEF_IPUT(4, Instruction::IPUT, 11u, 101u, 3u), 738 DEF_IPUT(5, Instruction::IPUT, 11u, 101u, 3u), 739 DEF_IGET(6, Instruction::IGET, 14u, 100u, 3u), // Differs from the top and the CONST. 740 741 DEF_IGET(3, Instruction::IGET_SHORT, 15u, 100u, 4u), 742 DEF_IGET(3, Instruction::IGET_CHAR, 16u, 100u, 5u), 743 DEF_IPUT(4, Instruction::IPUT_SHORT, 17u, 101u, 6u), // Clobbers field #4, not #5. 744 DEF_IGET(6, Instruction::IGET_SHORT, 18u, 100u, 4u), // Differs from the top. 745 DEF_IGET(6, Instruction::IGET_CHAR, 19u, 100u, 5u), // Same as the top. 746 747 DEF_CONST(4, Instruction::CONST, 20u, 3000), 748 DEF_IPUT(4, Instruction::IPUT, 20u, 100u, 7u), 749 DEF_IPUT(4, Instruction::IPUT, 20u, 101u, 8u), 750 DEF_CONST(5, Instruction::CONST, 23u, 3001), 751 DEF_IPUT(5, Instruction::IPUT, 23u, 100u, 7u), 752 DEF_IPUT(5, Instruction::IPUT, 23u, 101u, 8u), 753 DEF_IGET(6, Instruction::IGET, 26u, 100u, 7u), 754 DEF_IGET(6, Instruction::IGET, 27u, 101u, 8u), // Same value as read from field #7. 755 }; 756 757 PrepareIFields(ifields); 758 PrepareMIRs(mirs); 759 PerformGVN(); 760 ASSERT_EQ(arraysize(mirs), value_names_.size()); 761 EXPECT_NE(value_names_[0], value_names_[2]); 762 763 EXPECT_EQ(value_names_[3], value_names_[5]); 764 765 EXPECT_NE(value_names_[6], value_names_[9]); 766 EXPECT_NE(value_names_[7], value_names_[9]); 767 768 EXPECT_NE(value_names_[10], value_names_[14]); 769 EXPECT_NE(value_names_[10], value_names_[14]); 770 771 EXPECT_NE(value_names_[15], value_names_[18]); 772 EXPECT_EQ(value_names_[16], value_names_[19]); 773 774 EXPECT_EQ(value_names_[26], value_names_[27]); 775 } 776 777 TEST_F(GlobalValueNumberingTestDiamond, SFields) { 778 static const SFieldDef sfields[] = { 779 { 0u, 1u, 0u, false, kDexMemAccessWord }, 780 { 1u, 1u, 1u, false, kDexMemAccessWord }, 781 { 2u, 1u, 2u, false, kDexMemAccessWord }, 782 { 3u, 1u, 3u, false, kDexMemAccessWord }, 783 { 4u, 1u, 4u, false, kDexMemAccessShort }, 784 { 5u, 1u, 5u, false, kDexMemAccessChar }, 785 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 786 { 7u, 1u, 7u, false, kDexMemAccessWord }, 787 { 8u, 1u, 8u, false, kDexMemAccessWord }, 788 }; 789 static const MIRDef mirs[] = { 790 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 791 DEF_SGET(3, Instruction::SGET, 0u, 0u), 792 DEF_SGET(6, Instruction::SGET, 1u, 0u), // Same as at the top. 793 794 DEF_SGET(4, Instruction::SGET, 2u, 1u), 795 DEF_SGET(6, Instruction::SGET, 3u, 1u), // Same as at the left side. 796 797 DEF_SGET(3, Instruction::SGET, 4u, 2u), 798 DEF_CONST(5, Instruction::CONST, 5u, 100), 799 DEF_SPUT(5, Instruction::SPUT, 5u, 2u), 800 DEF_SGET(6, Instruction::SGET, 7u, 2u), // Differs from the top and the CONST. 801 802 DEF_SGET(3, Instruction::SGET, 8u, 3u), 803 DEF_CONST(3, Instruction::CONST, 9u, 200), 804 DEF_SPUT(4, Instruction::SPUT, 9u, 3u), 805 DEF_SPUT(5, Instruction::SPUT, 9u, 3u), 806 DEF_SGET(6, Instruction::SGET, 12u, 3u), // Differs from the top, equals the CONST. 807 808 DEF_SGET(3, Instruction::SGET_SHORT, 13u, 4u), 809 DEF_SGET(3, Instruction::SGET_CHAR, 14u, 5u), 810 DEF_SPUT(4, Instruction::SPUT_SHORT, 15u, 6u), // Clobbers field #4, not #5. 811 DEF_SGET(6, Instruction::SGET_SHORT, 16u, 4u), // Differs from the top. 812 DEF_SGET(6, Instruction::SGET_CHAR, 17u, 5u), // Same as the top. 813 814 DEF_CONST(4, Instruction::CONST, 18u, 300), 815 DEF_SPUT(4, Instruction::SPUT, 18u, 7u), 816 DEF_SPUT(4, Instruction::SPUT, 18u, 8u), 817 DEF_CONST(5, Instruction::CONST, 21u, 301), 818 DEF_SPUT(5, Instruction::SPUT, 21u, 7u), 819 DEF_SPUT(5, Instruction::SPUT, 21u, 8u), 820 DEF_SGET(6, Instruction::SGET, 24u, 7u), 821 DEF_SGET(6, Instruction::SGET, 25u, 8u), // Same value as read from field #7. 822 }; 823 824 PrepareSFields(sfields); 825 PrepareMIRs(mirs); 826 PerformGVN(); 827 ASSERT_EQ(arraysize(mirs), value_names_.size()); 828 EXPECT_EQ(value_names_[0], value_names_[1]); 829 830 EXPECT_EQ(value_names_[2], value_names_[3]); 831 832 EXPECT_NE(value_names_[4], value_names_[7]); 833 EXPECT_NE(value_names_[5], value_names_[7]); 834 835 EXPECT_NE(value_names_[8], value_names_[12]); 836 EXPECT_EQ(value_names_[9], value_names_[12]); 837 838 EXPECT_NE(value_names_[13], value_names_[16]); 839 EXPECT_EQ(value_names_[14], value_names_[17]); 840 841 EXPECT_EQ(value_names_[24], value_names_[25]); 842 } 843 844 TEST_F(GlobalValueNumberingTestDiamond, NonAliasingArrays) { 845 static const MIRDef mirs[] = { 846 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 847 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 100u), 848 DEF_AGET(3, Instruction::AGET, 1u, 100u, 101u), 849 DEF_AGET(6, Instruction::AGET, 2u, 100u, 101u), // Same as at the top. 850 851 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u), 852 DEF_IGET(4, Instruction::AGET, 4u, 200u, 201u), 853 DEF_IGET(6, Instruction::AGET, 5u, 200u, 201u), // Same as at the left side. 854 855 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 300u), 856 DEF_AGET(3, Instruction::AGET, 7u, 300u, 301u), 857 DEF_CONST(5, Instruction::CONST, 8u, 1000), 858 DEF_APUT(5, Instruction::APUT, 8u, 300u, 301u), 859 DEF_AGET(6, Instruction::AGET, 10u, 300u, 301u), // Differs from the top and the CONST. 860 861 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 400u), 862 DEF_AGET(3, Instruction::AGET, 12u, 400u, 401u), 863 DEF_CONST(3, Instruction::CONST, 13u, 2000), 864 DEF_APUT(4, Instruction::APUT, 13u, 400u, 401u), 865 DEF_APUT(5, Instruction::APUT, 13u, 400u, 401u), 866 DEF_AGET(6, Instruction::AGET, 16u, 400u, 401u), // Differs from the top, equals the CONST. 867 868 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 500u), 869 DEF_AGET(3, Instruction::AGET, 18u, 500u, 501u), 870 DEF_APUT(4, Instruction::APUT, 19u, 500u, 502u), // Clobbers value at index 501u. 871 DEF_AGET(6, Instruction::AGET, 20u, 500u, 501u), // Differs from the top. 872 873 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 600u), 874 DEF_CONST(4, Instruction::CONST, 22u, 3000), 875 DEF_APUT(4, Instruction::APUT, 22u, 600u, 601u), 876 DEF_APUT(4, Instruction::APUT, 22u, 600u, 602u), 877 DEF_CONST(5, Instruction::CONST, 25u, 3001), 878 DEF_APUT(5, Instruction::APUT, 25u, 600u, 601u), 879 DEF_APUT(5, Instruction::APUT, 25u, 600u, 602u), 880 DEF_AGET(6, Instruction::AGET, 28u, 600u, 601u), 881 DEF_AGET(6, Instruction::AGET, 29u, 600u, 602u), // Same value as read from index 601u. 882 883 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 700u), 884 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 701u), 885 DEF_AGET(3, Instruction::AGET, 32u, 700u, 702u), 886 DEF_APUT(4, Instruction::APUT, 33u, 701u, 702u), // Doesn't interfere with unrelated array. 887 DEF_AGET(6, Instruction::AGET, 34u, 700u, 702u), // Same value as at the top. 888 }; 889 890 PrepareMIRs(mirs); 891 PerformGVN(); 892 ASSERT_EQ(arraysize(mirs), value_names_.size()); 893 EXPECT_EQ(value_names_[1], value_names_[2]); 894 895 EXPECT_EQ(value_names_[4], value_names_[5]); 896 897 EXPECT_NE(value_names_[7], value_names_[10]); 898 EXPECT_NE(value_names_[8], value_names_[10]); 899 900 EXPECT_NE(value_names_[12], value_names_[16]); 901 EXPECT_EQ(value_names_[13], value_names_[16]); 902 903 EXPECT_NE(value_names_[18], value_names_[20]); 904 905 EXPECT_NE(value_names_[28], value_names_[22]); 906 EXPECT_NE(value_names_[28], value_names_[25]); 907 EXPECT_EQ(value_names_[28], value_names_[29]); 908 909 EXPECT_EQ(value_names_[32], value_names_[34]); 910 } 911 912 TEST_F(GlobalValueNumberingTestDiamond, AliasingArrays) { 913 static const MIRDef mirs[] = { 914 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 915 // NOTE: We're also testing that these tests really do not interfere with each other. 916 917 DEF_AGET(3, Instruction::AGET_BOOLEAN, 0u, 100u, 101u), 918 DEF_AGET(6, Instruction::AGET_BOOLEAN, 1u, 100u, 101u), // Same as at the top. 919 920 DEF_IGET(4, Instruction::AGET_OBJECT, 2u, 200u, 201u), 921 DEF_IGET(6, Instruction::AGET_OBJECT, 3u, 200u, 201u), // Same as at the left side. 922 923 DEF_AGET(3, Instruction::AGET_WIDE, 4u, 300u, 301u), 924 DEF_CONST(5, Instruction::CONST_WIDE, 6u, 1000), 925 DEF_APUT(5, Instruction::APUT_WIDE, 6u, 300u, 301u), 926 DEF_AGET(6, Instruction::AGET_WIDE, 8u, 300u, 301u), // Differs from the top and the CONST. 927 928 DEF_AGET(3, Instruction::AGET_SHORT, 10u, 400u, 401u), 929 DEF_CONST(3, Instruction::CONST, 11u, 2000), 930 DEF_APUT(4, Instruction::APUT_SHORT, 11u, 400u, 401u), 931 DEF_APUT(5, Instruction::APUT_SHORT, 11u, 400u, 401u), 932 DEF_AGET(6, Instruction::AGET_SHORT, 12u, 400u, 401u), // Differs from the top, == CONST. 933 934 DEF_AGET(3, Instruction::AGET_CHAR, 13u, 500u, 501u), 935 DEF_APUT(4, Instruction::APUT_CHAR, 14u, 500u, 502u), // Clobbers value at index 501u. 936 DEF_AGET(6, Instruction::AGET_CHAR, 15u, 500u, 501u), // Differs from the top. 937 938 DEF_AGET(3, Instruction::AGET_BYTE, 16u, 600u, 602u), 939 DEF_APUT(4, Instruction::APUT_BYTE, 17u, 601u, 602u), // Clobbers values in array 600u. 940 DEF_AGET(6, Instruction::AGET_BYTE, 18u, 600u, 602u), // Differs from the top. 941 942 DEF_CONST(4, Instruction::CONST, 19u, 3000), 943 DEF_APUT(4, Instruction::APUT, 19u, 700u, 701u), 944 DEF_APUT(4, Instruction::APUT, 19u, 700u, 702u), 945 DEF_CONST(5, Instruction::CONST, 22u, 3001), 946 DEF_APUT(5, Instruction::APUT, 22u, 700u, 701u), 947 DEF_APUT(5, Instruction::APUT, 22u, 700u, 702u), 948 DEF_AGET(6, Instruction::AGET, 25u, 700u, 701u), 949 DEF_AGET(6, Instruction::AGET, 26u, 700u, 702u), // Same value as read from index 601u. 950 }; 951 952 PrepareMIRs(mirs); 953 static const int32_t wide_sregs[] = { 4, 6, 8 }; 954 MarkAsWideSRegs(wide_sregs); 955 PerformGVN(); 956 ASSERT_EQ(arraysize(mirs), value_names_.size()); 957 EXPECT_EQ(value_names_[0], value_names_[1]); 958 959 EXPECT_EQ(value_names_[2], value_names_[3]); 960 961 EXPECT_NE(value_names_[4], value_names_[7]); 962 EXPECT_NE(value_names_[5], value_names_[7]); 963 964 EXPECT_NE(value_names_[8], value_names_[12]); 965 EXPECT_EQ(value_names_[9], value_names_[12]); 966 967 EXPECT_NE(value_names_[13], value_names_[15]); 968 969 EXPECT_NE(value_names_[16], value_names_[18]); 970 971 EXPECT_NE(value_names_[25], value_names_[19]); 972 EXPECT_NE(value_names_[25], value_names_[22]); 973 EXPECT_EQ(value_names_[25], value_names_[26]); 974 } 975 976 TEST_F(GlobalValueNumberingTestDiamond, Phi) { 977 static const MIRDef mirs[] = { 978 DEF_CONST(3, Instruction::CONST, 0u, 1000), 979 DEF_CONST(4, Instruction::CONST, 1u, 2000), 980 DEF_CONST(5, Instruction::CONST, 2u, 3000), 981 DEF_MOVE(4, Instruction::MOVE, 3u, 0u), 982 DEF_MOVE(4, Instruction::MOVE, 4u, 1u), 983 DEF_MOVE(5, Instruction::MOVE, 5u, 0u), 984 DEF_MOVE(5, Instruction::MOVE, 6u, 2u), 985 DEF_PHI2(6, 7u, 3u, 5u), // Same as CONST 0u (1000). 986 DEF_PHI2(6, 8u, 3u, 0u), // Same as CONST 0u (1000). 987 DEF_PHI2(6, 9u, 0u, 5u), // Same as CONST 0u (1000). 988 DEF_PHI2(6, 10u, 4u, 5u), // Merge 1u (2000) and 0u (1000). 989 DEF_PHI2(6, 11u, 1u, 5u), // Merge 1u (2000) and 0u (1000). 990 DEF_PHI2(6, 12u, 4u, 0u), // Merge 1u (2000) and 0u (1000). 991 DEF_PHI2(6, 13u, 1u, 0u), // Merge 1u (2000) and 0u (1000). 992 DEF_PHI2(6, 14u, 3u, 6u), // Merge 0u (1000) and 2u (3000). 993 DEF_PHI2(6, 15u, 0u, 6u), // Merge 0u (1000) and 2u (3000). 994 DEF_PHI2(6, 16u, 3u, 2u), // Merge 0u (1000) and 2u (3000). 995 DEF_PHI2(6, 17u, 0u, 2u), // Merge 0u (1000) and 2u (3000). 996 DEF_PHI2(6, 18u, 4u, 6u), // Merge 1u (2000) and 2u (3000). 997 DEF_PHI2(6, 19u, 1u, 6u), // Merge 1u (2000) and 2u (3000). 998 DEF_PHI2(6, 20u, 4u, 2u), // Merge 1u (2000) and 2u (3000). 999 DEF_PHI2(6, 21u, 1u, 2u), // Merge 1u (2000) and 2u (3000). 1000 }; 1001 1002 PrepareMIRs(mirs); 1003 PerformGVN(); 1004 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1005 EXPECT_EQ(value_names_[0], value_names_[7]); 1006 EXPECT_EQ(value_names_[0], value_names_[8]); 1007 EXPECT_EQ(value_names_[0], value_names_[9]); 1008 EXPECT_NE(value_names_[10], value_names_[0]); 1009 EXPECT_NE(value_names_[10], value_names_[1]); 1010 EXPECT_NE(value_names_[10], value_names_[2]); 1011 EXPECT_EQ(value_names_[10], value_names_[11]); 1012 EXPECT_EQ(value_names_[10], value_names_[12]); 1013 EXPECT_EQ(value_names_[10], value_names_[13]); 1014 EXPECT_NE(value_names_[14], value_names_[0]); 1015 EXPECT_NE(value_names_[14], value_names_[1]); 1016 EXPECT_NE(value_names_[14], value_names_[2]); 1017 EXPECT_NE(value_names_[14], value_names_[10]); 1018 EXPECT_EQ(value_names_[14], value_names_[15]); 1019 EXPECT_EQ(value_names_[14], value_names_[16]); 1020 EXPECT_EQ(value_names_[14], value_names_[17]); 1021 EXPECT_NE(value_names_[18], value_names_[0]); 1022 EXPECT_NE(value_names_[18], value_names_[1]); 1023 EXPECT_NE(value_names_[18], value_names_[2]); 1024 EXPECT_NE(value_names_[18], value_names_[10]); 1025 EXPECT_NE(value_names_[18], value_names_[14]); 1026 EXPECT_EQ(value_names_[18], value_names_[19]); 1027 EXPECT_EQ(value_names_[18], value_names_[20]); 1028 EXPECT_EQ(value_names_[18], value_names_[21]); 1029 } 1030 1031 TEST_F(GlobalValueNumberingTestDiamond, PhiWide) { 1032 static const MIRDef mirs[] = { 1033 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000), 1034 DEF_CONST_WIDE(4, Instruction::CONST_WIDE, 2u, 2000), 1035 DEF_CONST_WIDE(5, Instruction::CONST_WIDE, 4u, 3000), 1036 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 6u, 0u), 1037 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 8u, 2u), 1038 DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 10u, 0u), 1039 DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 12u, 4u), 1040 DEF_PHI2(6, 14u, 6u, 10u), // Same as CONST_WIDE 0u (1000). 1041 DEF_PHI2(6, 15u, 7u, 11u), // Same as CONST_WIDE 0u (1000), high word. 1042 DEF_PHI2(6, 16u, 6u, 0u), // Same as CONST_WIDE 0u (1000). 1043 DEF_PHI2(6, 17u, 7u, 1u), // Same as CONST_WIDE 0u (1000), high word. 1044 DEF_PHI2(6, 18u, 0u, 10u), // Same as CONST_WIDE 0u (1000). 1045 DEF_PHI2(6, 19u, 1u, 11u), // Same as CONST_WIDE 0u (1000), high word. 1046 DEF_PHI2(6, 20u, 8u, 10u), // Merge 2u (2000) and 0u (1000). 1047 DEF_PHI2(6, 21u, 9u, 11u), // Merge 2u (2000) and 0u (1000), high word. 1048 DEF_PHI2(6, 22u, 2u, 10u), // Merge 2u (2000) and 0u (1000). 1049 DEF_PHI2(6, 23u, 3u, 11u), // Merge 2u (2000) and 0u (1000), high word. 1050 DEF_PHI2(6, 24u, 8u, 0u), // Merge 2u (2000) and 0u (1000). 1051 DEF_PHI2(6, 25u, 9u, 1u), // Merge 2u (2000) and 0u (1000), high word. 1052 DEF_PHI2(6, 26u, 2u, 0u), // Merge 2u (2000) and 0u (1000). 1053 DEF_PHI2(6, 27u, 5u, 1u), // Merge 2u (2000) and 0u (1000), high word. 1054 DEF_PHI2(6, 28u, 6u, 12u), // Merge 0u (1000) and 4u (3000). 1055 DEF_PHI2(6, 29u, 7u, 13u), // Merge 0u (1000) and 4u (3000), high word. 1056 DEF_PHI2(6, 30u, 0u, 12u), // Merge 0u (1000) and 4u (3000). 1057 DEF_PHI2(6, 31u, 1u, 13u), // Merge 0u (1000) and 4u (3000), high word. 1058 DEF_PHI2(6, 32u, 6u, 4u), // Merge 0u (1000) and 4u (3000). 1059 DEF_PHI2(6, 33u, 7u, 5u), // Merge 0u (1000) and 4u (3000), high word. 1060 DEF_PHI2(6, 34u, 0u, 4u), // Merge 0u (1000) and 4u (3000). 1061 DEF_PHI2(6, 35u, 1u, 5u), // Merge 0u (1000) and 4u (3000), high word. 1062 DEF_PHI2(6, 36u, 8u, 12u), // Merge 2u (2000) and 4u (3000). 1063 DEF_PHI2(6, 37u, 9u, 13u), // Merge 2u (2000) and 4u (3000), high word. 1064 DEF_PHI2(6, 38u, 2u, 12u), // Merge 2u (2000) and 4u (3000). 1065 DEF_PHI2(6, 39u, 3u, 13u), // Merge 2u (2000) and 4u (3000), high word. 1066 DEF_PHI2(6, 40u, 8u, 4u), // Merge 2u (2000) and 4u (3000). 1067 DEF_PHI2(6, 41u, 9u, 5u), // Merge 2u (2000) and 4u (3000), high word. 1068 DEF_PHI2(6, 42u, 2u, 4u), // Merge 2u (2000) and 4u (3000). 1069 DEF_PHI2(6, 43u, 3u, 5u), // Merge 2u (2000) and 4u (3000), high word. 1070 }; 1071 1072 PrepareMIRs(mirs); 1073 for (size_t i = 0u; i != arraysize(mirs); ++i) { 1074 if ((mirs_[i].ssa_rep->defs[0] % 2) == 0) { 1075 const int32_t wide_sregs[] = { mirs_[i].ssa_rep->defs[0] }; 1076 MarkAsWideSRegs(wide_sregs); 1077 } 1078 } 1079 PerformGVN(); 1080 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1081 EXPECT_EQ(value_names_[0], value_names_[7]); 1082 EXPECT_EQ(value_names_[0], value_names_[9]); 1083 EXPECT_EQ(value_names_[0], value_names_[11]); 1084 EXPECT_NE(value_names_[13], value_names_[0]); 1085 EXPECT_NE(value_names_[13], value_names_[1]); 1086 EXPECT_NE(value_names_[13], value_names_[2]); 1087 EXPECT_EQ(value_names_[13], value_names_[15]); 1088 EXPECT_EQ(value_names_[13], value_names_[17]); 1089 EXPECT_EQ(value_names_[13], value_names_[19]); 1090 EXPECT_NE(value_names_[21], value_names_[0]); 1091 EXPECT_NE(value_names_[21], value_names_[1]); 1092 EXPECT_NE(value_names_[21], value_names_[2]); 1093 EXPECT_NE(value_names_[21], value_names_[13]); 1094 EXPECT_EQ(value_names_[21], value_names_[23]); 1095 EXPECT_EQ(value_names_[21], value_names_[25]); 1096 EXPECT_EQ(value_names_[21], value_names_[27]); 1097 EXPECT_NE(value_names_[29], value_names_[0]); 1098 EXPECT_NE(value_names_[29], value_names_[1]); 1099 EXPECT_NE(value_names_[29], value_names_[2]); 1100 EXPECT_NE(value_names_[29], value_names_[13]); 1101 EXPECT_NE(value_names_[29], value_names_[21]); 1102 EXPECT_EQ(value_names_[29], value_names_[31]); 1103 EXPECT_EQ(value_names_[29], value_names_[33]); 1104 EXPECT_EQ(value_names_[29], value_names_[35]); 1105 // High words should get kNoValue. 1106 EXPECT_EQ(value_names_[8], kNoValue); 1107 EXPECT_EQ(value_names_[10], kNoValue); 1108 EXPECT_EQ(value_names_[12], kNoValue); 1109 EXPECT_EQ(value_names_[14], kNoValue); 1110 EXPECT_EQ(value_names_[16], kNoValue); 1111 EXPECT_EQ(value_names_[18], kNoValue); 1112 EXPECT_EQ(value_names_[20], kNoValue); 1113 EXPECT_EQ(value_names_[22], kNoValue); 1114 EXPECT_EQ(value_names_[24], kNoValue); 1115 EXPECT_EQ(value_names_[26], kNoValue); 1116 EXPECT_EQ(value_names_[28], kNoValue); 1117 EXPECT_EQ(value_names_[30], kNoValue); 1118 EXPECT_EQ(value_names_[32], kNoValue); 1119 EXPECT_EQ(value_names_[34], kNoValue); 1120 EXPECT_EQ(value_names_[36], kNoValue); 1121 } 1122 1123 TEST_F(GlobalValueNumberingTestLoop, NonAliasingIFields) { 1124 static const IFieldDef ifields[] = { 1125 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1126 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1127 { 2u, 1u, 2u, false, kDexMemAccessWord }, 1128 { 3u, 1u, 3u, false, kDexMemAccessWord }, 1129 { 4u, 1u, 4u, false, kDexMemAccessWord }, 1130 { 5u, 1u, 5u, false, kDexMemAccessShort }, 1131 { 6u, 1u, 6u, false, kDexMemAccessChar }, 1132 { 7u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 1133 { 8u, 1u, 8u, false, kDexMemAccessWord }, 1134 { 9u, 0u, 0u, false, kDexMemAccessWord }, // Unresolved. 1135 { 10u, 1u, 10u, false, kDexMemAccessWord }, 1136 { 11u, 1u, 11u, false, kDexMemAccessWord }, 1137 }; 1138 static const MIRDef mirs[] = { 1139 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 1140 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 100u), 1141 DEF_IGET(3, Instruction::IGET, 1u, 100u, 0u), 1142 DEF_IGET(4, Instruction::IGET, 2u, 100u, 0u), // Same as at the top. 1143 DEF_IGET(5, Instruction::IGET, 3u, 100u, 0u), // Same as at the top. 1144 1145 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 200u), 1146 DEF_IGET(3, Instruction::IGET, 5u, 200u, 1u), 1147 DEF_IGET(4, Instruction::IGET, 6u, 200u, 1u), // Differs from top... 1148 DEF_IPUT(4, Instruction::IPUT, 7u, 200u, 1u), // Because of this IPUT. 1149 DEF_IGET(5, Instruction::IGET, 8u, 200u, 1u), // Differs from top and the loop IGET. 1150 1151 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 300u), 1152 DEF_IGET(3, Instruction::IGET, 10u, 300u, 2u), 1153 DEF_IPUT(4, Instruction::IPUT, 11u, 300u, 2u), // Because of this IPUT... 1154 DEF_IGET(4, Instruction::IGET, 12u, 300u, 2u), // Differs from top. 1155 DEF_IGET(5, Instruction::IGET, 13u, 300u, 2u), // Differs from top but same as the loop IGET. 1156 1157 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 400u), 1158 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 401u), 1159 DEF_CONST(3, Instruction::CONST, 16u, 3000), 1160 DEF_IPUT(3, Instruction::IPUT, 16u, 400u, 3u), 1161 DEF_IPUT(3, Instruction::IPUT, 16u, 400u, 4u), 1162 DEF_IPUT(3, Instruction::IPUT, 16u, 401u, 3u), 1163 DEF_IGET(4, Instruction::IGET, 20u, 400u, 3u), // Differs from 16u and 23u. 1164 DEF_IGET(4, Instruction::IGET, 21u, 400u, 4u), // Same as 20u. 1165 DEF_IGET(4, Instruction::IGET, 22u, 401u, 3u), // Same as 20u. 1166 DEF_CONST(4, Instruction::CONST, 23u, 4000), 1167 DEF_IPUT(4, Instruction::IPUT, 23u, 400u, 3u), 1168 DEF_IPUT(4, Instruction::IPUT, 23u, 400u, 4u), 1169 DEF_IPUT(4, Instruction::IPUT, 23u, 401u, 3u), 1170 DEF_IGET(5, Instruction::IGET, 27u, 400u, 3u), // Differs from 16u and 20u... 1171 DEF_IGET(5, Instruction::IGET, 28u, 400u, 4u), // and same as the CONST 23u 1172 DEF_IGET(5, Instruction::IGET, 29u, 400u, 4u), // and same as the CONST 23u. 1173 1174 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 500u), 1175 DEF_IGET(3, Instruction::IGET_SHORT, 31u, 500u, 5u), 1176 DEF_IGET(3, Instruction::IGET_CHAR, 32u, 500u, 6u), 1177 DEF_IPUT(4, Instruction::IPUT_SHORT, 33u, 500u, 7u), // Clobbers field #5, not #6. 1178 DEF_IGET(5, Instruction::IGET_SHORT, 34u, 500u, 5u), // Differs from the top. 1179 DEF_IGET(5, Instruction::IGET_CHAR, 35u, 500u, 6u), // Same as the top. 1180 1181 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 600u), 1182 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 601u), 1183 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 602u), 1184 DEF_IGET(3, Instruction::IGET, 39u, 600u, 8u), 1185 DEF_IGET(3, Instruction::IGET, 40u, 601u, 8u), 1186 DEF_IPUT(4, Instruction::IPUT, 41u, 602u, 9u), // Doesn't clobber field #8 for other refs. 1187 DEF_IGET(5, Instruction::IGET, 42u, 600u, 8u), // Same as the top. 1188 DEF_IGET(5, Instruction::IGET, 43u, 601u, 8u), // Same as the top. 1189 1190 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 700u), 1191 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 701u), 1192 DEF_CONST(3, Instruction::CONST, 46u, 3000), 1193 DEF_IPUT(3, Instruction::IPUT, 46u, 700u, 10u), 1194 DEF_IPUT(3, Instruction::IPUT, 46u, 700u, 11u), 1195 DEF_IPUT(3, Instruction::IPUT, 46u, 701u, 10u), 1196 DEF_IGET(4, Instruction::IGET, 50u, 700u, 10u), // Differs from the CONSTs 46u and 53u. 1197 DEF_IGET(4, Instruction::IGET, 51u, 700u, 11u), // Same as 50u. 1198 DEF_IGET(4, Instruction::IGET, 52u, 701u, 10u), // Same as 50u. 1199 DEF_CONST(4, Instruction::CONST, 53u, 3001), 1200 DEF_IPUT(4, Instruction::IPUT, 53u, 700u, 10u), 1201 DEF_IPUT(4, Instruction::IPUT, 53u, 700u, 11u), 1202 DEF_IPUT(4, Instruction::IPUT, 53u, 701u, 10u), 1203 DEF_IGET(5, Instruction::IGET, 57u, 700u, 10u), // Same as the CONST 53u. 1204 DEF_IGET(5, Instruction::IGET, 58u, 700u, 11u), // Same as the CONST 53u. 1205 DEF_IGET(5, Instruction::IGET, 59u, 701u, 10u), // Same as the CONST 53u. 1206 }; 1207 1208 PrepareIFields(ifields); 1209 PrepareMIRs(mirs); 1210 PerformGVN(); 1211 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1212 EXPECT_EQ(value_names_[1], value_names_[2]); 1213 EXPECT_EQ(value_names_[1], value_names_[3]); 1214 1215 EXPECT_NE(value_names_[5], value_names_[6]); 1216 EXPECT_NE(value_names_[5], value_names_[7]); 1217 EXPECT_NE(value_names_[6], value_names_[7]); 1218 1219 EXPECT_NE(value_names_[10], value_names_[12]); 1220 EXPECT_EQ(value_names_[12], value_names_[13]); 1221 1222 EXPECT_NE(value_names_[20], value_names_[16]); 1223 EXPECT_NE(value_names_[20], value_names_[23]); 1224 EXPECT_EQ(value_names_[20], value_names_[21]); 1225 EXPECT_EQ(value_names_[20], value_names_[22]); 1226 EXPECT_NE(value_names_[27], value_names_[16]); 1227 EXPECT_NE(value_names_[27], value_names_[20]); 1228 EXPECT_EQ(value_names_[27], value_names_[28]); 1229 EXPECT_EQ(value_names_[27], value_names_[29]); 1230 1231 EXPECT_NE(value_names_[31], value_names_[34]); 1232 EXPECT_EQ(value_names_[32], value_names_[35]); 1233 1234 EXPECT_EQ(value_names_[39], value_names_[42]); 1235 EXPECT_EQ(value_names_[40], value_names_[43]); 1236 1237 EXPECT_NE(value_names_[50], value_names_[46]); 1238 EXPECT_NE(value_names_[50], value_names_[53]); 1239 EXPECT_EQ(value_names_[50], value_names_[51]); 1240 EXPECT_EQ(value_names_[50], value_names_[52]); 1241 EXPECT_EQ(value_names_[57], value_names_[53]); 1242 EXPECT_EQ(value_names_[58], value_names_[53]); 1243 EXPECT_EQ(value_names_[59], value_names_[53]); 1244 } 1245 1246 TEST_F(GlobalValueNumberingTestLoop, AliasingIFieldsSingleObject) { 1247 static const IFieldDef ifields[] = { 1248 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1249 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1250 { 2u, 1u, 2u, false, kDexMemAccessWord }, 1251 { 3u, 1u, 3u, false, kDexMemAccessWord }, 1252 { 4u, 1u, 4u, false, kDexMemAccessWord }, 1253 { 5u, 1u, 5u, false, kDexMemAccessShort }, 1254 { 6u, 1u, 6u, false, kDexMemAccessChar }, 1255 { 7u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 1256 }; 1257 static const MIRDef mirs[] = { 1258 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 1259 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u), 1260 DEF_IGET(4, Instruction::IGET, 1u, 100u, 0u), // Same as at the top. 1261 DEF_IGET(5, Instruction::IGET, 2u, 100u, 0u), // Same as at the top. 1262 1263 DEF_IGET(3, Instruction::IGET, 3u, 100u, 1u), 1264 DEF_IGET(4, Instruction::IGET, 4u, 100u, 1u), // Differs from top... 1265 DEF_IPUT(4, Instruction::IPUT, 5u, 100u, 1u), // Because of this IPUT. 1266 DEF_IGET(5, Instruction::IGET, 6u, 100u, 1u), // Differs from top and the loop IGET. 1267 1268 DEF_IGET(3, Instruction::IGET, 7u, 100u, 2u), 1269 DEF_IPUT(4, Instruction::IPUT, 8u, 100u, 2u), // Because of this IPUT... 1270 DEF_IGET(4, Instruction::IGET, 9u, 100u, 2u), // Differs from top. 1271 DEF_IGET(5, Instruction::IGET, 10u, 100u, 2u), // Differs from top but same as the loop IGET. 1272 1273 DEF_CONST(3, Instruction::CONST, 11u, 3000), 1274 DEF_IPUT(3, Instruction::IPUT, 11u, 100u, 3u), 1275 DEF_IPUT(3, Instruction::IPUT, 11u, 100u, 4u), 1276 DEF_IGET(4, Instruction::IGET, 14u, 100u, 3u), // Differs from 11u and 16u. 1277 DEF_IGET(4, Instruction::IGET, 15u, 100u, 4u), // Same as 14u. 1278 DEF_CONST(4, Instruction::CONST, 16u, 4000), 1279 DEF_IPUT(4, Instruction::IPUT, 16u, 100u, 3u), 1280 DEF_IPUT(4, Instruction::IPUT, 16u, 100u, 4u), 1281 DEF_IGET(5, Instruction::IGET, 19u, 100u, 3u), // Differs from 11u and 14u... 1282 DEF_IGET(5, Instruction::IGET, 20u, 100u, 4u), // and same as the CONST 16u. 1283 1284 DEF_IGET(3, Instruction::IGET_SHORT, 21u, 100u, 5u), 1285 DEF_IGET(3, Instruction::IGET_CHAR, 22u, 100u, 6u), 1286 DEF_IPUT(4, Instruction::IPUT_SHORT, 23u, 100u, 7u), // Clobbers field #5, not #6. 1287 DEF_IGET(5, Instruction::IGET_SHORT, 24u, 100u, 5u), // Differs from the top. 1288 DEF_IGET(5, Instruction::IGET_CHAR, 25u, 100u, 6u), // Same as the top. 1289 }; 1290 1291 PrepareIFields(ifields); 1292 PrepareMIRs(mirs); 1293 PerformGVN(); 1294 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1295 EXPECT_EQ(value_names_[0], value_names_[1]); 1296 EXPECT_EQ(value_names_[0], value_names_[2]); 1297 1298 EXPECT_NE(value_names_[3], value_names_[4]); 1299 EXPECT_NE(value_names_[3], value_names_[6]); 1300 EXPECT_NE(value_names_[4], value_names_[6]); 1301 1302 EXPECT_NE(value_names_[7], value_names_[9]); 1303 EXPECT_EQ(value_names_[9], value_names_[10]); 1304 1305 EXPECT_NE(value_names_[14], value_names_[11]); 1306 EXPECT_NE(value_names_[14], value_names_[16]); 1307 EXPECT_EQ(value_names_[14], value_names_[15]); 1308 EXPECT_NE(value_names_[19], value_names_[11]); 1309 EXPECT_NE(value_names_[19], value_names_[14]); 1310 EXPECT_EQ(value_names_[19], value_names_[16]); 1311 EXPECT_EQ(value_names_[19], value_names_[20]); 1312 1313 EXPECT_NE(value_names_[21], value_names_[24]); 1314 EXPECT_EQ(value_names_[22], value_names_[25]); 1315 } 1316 1317 TEST_F(GlobalValueNumberingTestLoop, AliasingIFieldsTwoObjects) { 1318 static const IFieldDef ifields[] = { 1319 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1320 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1321 { 2u, 1u, 2u, false, kDexMemAccessWord }, 1322 { 3u, 1u, 3u, false, kDexMemAccessShort }, 1323 { 4u, 1u, 4u, false, kDexMemAccessChar }, 1324 { 5u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved. 1325 { 6u, 1u, 6u, false, kDexMemAccessWord }, 1326 { 7u, 1u, 7u, false, kDexMemAccessWord }, 1327 }; 1328 static const MIRDef mirs[] = { 1329 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 1330 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u), 1331 DEF_IPUT(4, Instruction::IPUT, 1u, 101u, 0u), // May alias with the IGET at the top. 1332 DEF_IGET(5, Instruction::IGET, 2u, 100u, 0u), // Differs from the top. 1333 1334 DEF_IGET(3, Instruction::IGET, 3u, 100u, 1u), 1335 DEF_IPUT(4, Instruction::IPUT, 3u, 101u, 1u), // If aliasing, stores the same value. 1336 DEF_IGET(5, Instruction::IGET, 5u, 100u, 1u), // Same as the top. 1337 1338 DEF_IGET(3, Instruction::IGET, 6u, 100u, 2u), 1339 DEF_CONST(4, Instruction::CONST, 7u, 1000), 1340 DEF_IPUT(4, Instruction::IPUT, 7u, 101u, 2u), 1341 DEF_IGET(5, Instruction::IGET, 9u, 100u, 2u), // Differs from the top and the CONST. 1342 1343 DEF_IGET(3, Instruction::IGET_SHORT, 10u, 100u, 3u), 1344 DEF_IGET(3, Instruction::IGET_CHAR, 11u, 100u, 4u), 1345 DEF_IPUT(4, Instruction::IPUT_SHORT, 12u, 101u, 5u), // Clobbers field #3, not #4. 1346 DEF_IGET(5, Instruction::IGET_SHORT, 13u, 100u, 3u), // Differs from the top. 1347 DEF_IGET(5, Instruction::IGET_CHAR, 14u, 100u, 4u), // Same as the top. 1348 1349 DEF_CONST(3, Instruction::CONST, 15u, 3000), 1350 DEF_IPUT(3, Instruction::IPUT, 15u, 100u, 6u), 1351 DEF_IPUT(3, Instruction::IPUT, 15u, 100u, 7u), 1352 DEF_IPUT(3, Instruction::IPUT, 15u, 101u, 6u), 1353 DEF_IGET(4, Instruction::IGET, 19u, 100u, 6u), // Differs from CONSTs 15u and 22u. 1354 DEF_IGET(4, Instruction::IGET, 20u, 100u, 7u), // Same value as 19u. 1355 DEF_IGET(4, Instruction::IGET, 21u, 101u, 6u), // Same value as read from field #7. 1356 DEF_CONST(4, Instruction::CONST, 22u, 3001), 1357 DEF_IPUT(4, Instruction::IPUT, 22u, 100u, 6u), 1358 DEF_IPUT(4, Instruction::IPUT, 22u, 100u, 7u), 1359 DEF_IPUT(4, Instruction::IPUT, 22u, 101u, 6u), 1360 DEF_IGET(5, Instruction::IGET, 26u, 100u, 6u), // Same as CONST 22u. 1361 DEF_IGET(5, Instruction::IGET, 27u, 100u, 7u), // Same as CONST 22u. 1362 DEF_IGET(5, Instruction::IGET, 28u, 101u, 6u), // Same as CONST 22u. 1363 }; 1364 1365 PrepareIFields(ifields); 1366 PrepareMIRs(mirs); 1367 PerformGVN(); 1368 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1369 EXPECT_NE(value_names_[0], value_names_[2]); 1370 1371 EXPECT_EQ(value_names_[3], value_names_[5]); 1372 1373 EXPECT_NE(value_names_[6], value_names_[9]); 1374 EXPECT_NE(value_names_[7], value_names_[9]); 1375 1376 EXPECT_NE(value_names_[10], value_names_[13]); 1377 EXPECT_EQ(value_names_[11], value_names_[14]); 1378 1379 EXPECT_NE(value_names_[19], value_names_[15]); 1380 EXPECT_NE(value_names_[19], value_names_[22]); 1381 EXPECT_EQ(value_names_[22], value_names_[26]); 1382 EXPECT_EQ(value_names_[22], value_names_[27]); 1383 EXPECT_EQ(value_names_[22], value_names_[28]); 1384 } 1385 1386 TEST_F(GlobalValueNumberingTestLoop, IFieldToBaseDependency) { 1387 static const IFieldDef ifields[] = { 1388 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1389 }; 1390 static const MIRDef mirs[] = { 1391 // For the IGET that loads sreg 3u using base 2u, the following IPUT creates a dependency 1392 // from the field value to the base. However, this dependency does not result in an 1393 // infinite loop since the merge of the field value for base 0u gets assigned a value name 1394 // based only on the base 0u, not on the actual value, and breaks the dependency cycle. 1395 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u), 1396 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 1397 DEF_IGET(4, Instruction::IGET, 2u, 0u, 0u), 1398 DEF_IGET(4, Instruction::IGET, 3u, 2u, 0u), 1399 DEF_IPUT(4, Instruction::IPUT, 3u, 0u, 0u), 1400 DEF_IGET(5, Instruction::IGET, 5u, 0u, 0u), 1401 }; 1402 1403 PrepareIFields(ifields); 1404 PrepareMIRs(mirs); 1405 PerformGVN(); 1406 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1407 EXPECT_NE(value_names_[1], value_names_[2]); 1408 EXPECT_EQ(value_names_[3], value_names_[5]); 1409 } 1410 1411 TEST_F(GlobalValueNumberingTestLoop, SFields) { 1412 static const SFieldDef sfields[] = { 1413 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1414 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1415 { 2u, 1u, 2u, false, kDexMemAccessWord }, 1416 }; 1417 static const MIRDef mirs[] = { 1418 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 1419 DEF_SGET(3, Instruction::SGET, 0u, 0u), 1420 DEF_SGET(4, Instruction::SGET, 1u, 0u), // Same as at the top. 1421 DEF_SGET(5, Instruction::SGET, 2u, 0u), // Same as at the top. 1422 1423 DEF_SGET(3, Instruction::SGET, 3u, 1u), 1424 DEF_SGET(4, Instruction::SGET, 4u, 1u), // Differs from top... 1425 DEF_SPUT(4, Instruction::SPUT, 5u, 1u), // Because of this SPUT. 1426 DEF_SGET(5, Instruction::SGET, 6u, 1u), // Differs from top and the loop SGET. 1427 1428 DEF_SGET(3, Instruction::SGET, 7u, 2u), 1429 DEF_SPUT(4, Instruction::SPUT, 8u, 2u), // Because of this SPUT... 1430 DEF_SGET(4, Instruction::SGET, 9u, 2u), // Differs from top. 1431 DEF_SGET(5, Instruction::SGET, 10u, 2u), // Differs from top but same as the loop SGET. 1432 }; 1433 1434 PrepareSFields(sfields); 1435 PrepareMIRs(mirs); 1436 PerformGVN(); 1437 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1438 EXPECT_EQ(value_names_[0], value_names_[1]); 1439 EXPECT_EQ(value_names_[0], value_names_[2]); 1440 1441 EXPECT_NE(value_names_[3], value_names_[4]); 1442 EXPECT_NE(value_names_[3], value_names_[6]); 1443 EXPECT_NE(value_names_[4], value_names_[5]); 1444 1445 EXPECT_NE(value_names_[7], value_names_[9]); 1446 EXPECT_EQ(value_names_[9], value_names_[10]); 1447 } 1448 1449 TEST_F(GlobalValueNumberingTestLoop, NonAliasingArrays) { 1450 static const MIRDef mirs[] = { 1451 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 1452 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 100u), 1453 DEF_AGET(3, Instruction::AGET, 1u, 100u, 101u), 1454 DEF_AGET(4, Instruction::AGET, 2u, 100u, 101u), // Same as at the top. 1455 DEF_AGET(5, Instruction::AGET, 3u, 100u, 101u), // Same as at the top. 1456 1457 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u), 1458 DEF_AGET(3, Instruction::AGET, 5u, 200u, 201u), 1459 DEF_AGET(4, Instruction::AGET, 6u, 200u, 201u), // Differs from top... 1460 DEF_APUT(4, Instruction::APUT, 7u, 200u, 201u), // Because of this IPUT. 1461 DEF_AGET(5, Instruction::AGET, 8u, 200u, 201u), // Differs from top and the loop AGET. 1462 1463 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 300u), 1464 DEF_AGET(3, Instruction::AGET, 10u, 300u, 301u), 1465 DEF_APUT(4, Instruction::APUT, 11u, 300u, 301u), // Because of this IPUT... 1466 DEF_AGET(4, Instruction::AGET, 12u, 300u, 301u), // Differs from top. 1467 DEF_AGET(5, Instruction::AGET, 13u, 300u, 301u), // Differs from top but == the loop AGET. 1468 1469 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 400u), 1470 DEF_CONST(3, Instruction::CONST, 15u, 3000), 1471 DEF_APUT(3, Instruction::APUT, 15u, 400u, 401u), 1472 DEF_APUT(3, Instruction::APUT, 15u, 400u, 402u), 1473 DEF_AGET(4, Instruction::AGET, 18u, 400u, 401u), // Differs from 15u and 20u. 1474 DEF_AGET(4, Instruction::AGET, 19u, 400u, 402u), // Same as 18u. 1475 DEF_CONST(4, Instruction::CONST, 20u, 4000), 1476 DEF_APUT(4, Instruction::APUT, 20u, 400u, 401u), 1477 DEF_APUT(4, Instruction::APUT, 20u, 400u, 402u), 1478 DEF_AGET(5, Instruction::AGET, 23u, 400u, 401u), // Differs from 15u and 18u... 1479 DEF_AGET(5, Instruction::AGET, 24u, 400u, 402u), // and same as the CONST 20u. 1480 1481 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 500u), 1482 DEF_AGET(3, Instruction::AGET, 26u, 500u, 501u), 1483 DEF_APUT(4, Instruction::APUT, 27u, 500u, 502u), // Clobbers element at index 501u. 1484 DEF_AGET(5, Instruction::AGET, 28u, 500u, 501u), // Differs from the top. 1485 }; 1486 1487 PrepareMIRs(mirs); 1488 PerformGVN(); 1489 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1490 EXPECT_EQ(value_names_[1], value_names_[2]); 1491 EXPECT_EQ(value_names_[1], value_names_[3]); 1492 1493 EXPECT_NE(value_names_[5], value_names_[6]); 1494 EXPECT_NE(value_names_[5], value_names_[8]); 1495 EXPECT_NE(value_names_[6], value_names_[8]); 1496 1497 EXPECT_NE(value_names_[10], value_names_[12]); 1498 EXPECT_EQ(value_names_[12], value_names_[13]); 1499 1500 EXPECT_NE(value_names_[18], value_names_[15]); 1501 EXPECT_NE(value_names_[18], value_names_[20]); 1502 EXPECT_EQ(value_names_[18], value_names_[19]); 1503 EXPECT_NE(value_names_[23], value_names_[15]); 1504 EXPECT_NE(value_names_[23], value_names_[18]); 1505 EXPECT_EQ(value_names_[23], value_names_[20]); 1506 EXPECT_EQ(value_names_[23], value_names_[24]); 1507 1508 EXPECT_NE(value_names_[26], value_names_[28]); 1509 } 1510 1511 TEST_F(GlobalValueNumberingTestLoop, AliasingArrays) { 1512 static const MIRDef mirs[] = { 1513 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks. 1514 DEF_AGET(3, Instruction::AGET_WIDE, 0u, 100u, 101u), 1515 DEF_AGET(4, Instruction::AGET_WIDE, 2u, 100u, 101u), // Same as at the top. 1516 DEF_AGET(5, Instruction::AGET_WIDE, 4u, 100u, 101u), // Same as at the top. 1517 1518 DEF_AGET(3, Instruction::AGET_BYTE, 6u, 200u, 201u), 1519 DEF_AGET(4, Instruction::AGET_BYTE, 7u, 200u, 201u), // Differs from top... 1520 DEF_APUT(4, Instruction::APUT_BYTE, 8u, 200u, 201u), // Because of this IPUT. 1521 DEF_AGET(5, Instruction::AGET_BYTE, 9u, 200u, 201u), // Differs from top and the loop AGET. 1522 1523 DEF_AGET(3, Instruction::AGET, 10u, 300u, 301u), 1524 DEF_APUT(4, Instruction::APUT, 11u, 300u, 301u), // Because of this IPUT... 1525 DEF_AGET(4, Instruction::AGET, 12u, 300u, 301u), // Differs from top. 1526 DEF_AGET(5, Instruction::AGET, 13u, 300u, 301u), // Differs from top but == the loop AGET. 1527 1528 DEF_CONST(3, Instruction::CONST, 14u, 3000), 1529 DEF_APUT(3, Instruction::APUT_CHAR, 14u, 400u, 401u), 1530 DEF_APUT(3, Instruction::APUT_CHAR, 14u, 400u, 402u), 1531 DEF_AGET(4, Instruction::AGET_CHAR, 15u, 400u, 401u), // Differs from 11u and 16u. 1532 DEF_AGET(4, Instruction::AGET_CHAR, 16u, 400u, 402u), // Same as 14u. 1533 DEF_CONST(4, Instruction::CONST, 17u, 4000), 1534 DEF_APUT(4, Instruction::APUT_CHAR, 17u, 400u, 401u), 1535 DEF_APUT(4, Instruction::APUT_CHAR, 17u, 400u, 402u), 1536 DEF_AGET(5, Instruction::AGET_CHAR, 19u, 400u, 401u), // Differs from 11u and 14u... 1537 DEF_AGET(5, Instruction::AGET_CHAR, 20u, 400u, 402u), // and same as the CONST 16u. 1538 1539 DEF_AGET(3, Instruction::AGET_SHORT, 21u, 500u, 501u), 1540 DEF_APUT(4, Instruction::APUT_SHORT, 22u, 500u, 502u), // Clobbers element at index 501u. 1541 DEF_AGET(5, Instruction::AGET_SHORT, 23u, 500u, 501u), // Differs from the top. 1542 1543 DEF_AGET(3, Instruction::AGET_OBJECT, 24u, 600u, 601u), 1544 DEF_APUT(4, Instruction::APUT_OBJECT, 25u, 601u, 602u), // Clobbers 600u/601u. 1545 DEF_AGET(5, Instruction::AGET_OBJECT, 26u, 600u, 601u), // Differs from the top. 1546 1547 DEF_AGET(3, Instruction::AGET_BOOLEAN, 27u, 700u, 701u), 1548 DEF_APUT(4, Instruction::APUT_BOOLEAN, 27u, 701u, 702u), // Storing the same value. 1549 DEF_AGET(5, Instruction::AGET_BOOLEAN, 29u, 700u, 701u), // Differs from the top. 1550 }; 1551 1552 PrepareMIRs(mirs); 1553 static const int32_t wide_sregs[] = { 0, 2, 4 }; 1554 MarkAsWideSRegs(wide_sregs); 1555 PerformGVN(); 1556 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1557 EXPECT_EQ(value_names_[0], value_names_[1]); 1558 EXPECT_EQ(value_names_[0], value_names_[2]); 1559 1560 EXPECT_NE(value_names_[3], value_names_[4]); 1561 EXPECT_NE(value_names_[3], value_names_[6]); 1562 EXPECT_NE(value_names_[4], value_names_[6]); 1563 1564 EXPECT_NE(value_names_[7], value_names_[9]); 1565 EXPECT_EQ(value_names_[9], value_names_[10]); 1566 1567 EXPECT_NE(value_names_[14], value_names_[11]); 1568 EXPECT_NE(value_names_[14], value_names_[16]); 1569 EXPECT_EQ(value_names_[14], value_names_[15]); 1570 EXPECT_NE(value_names_[19], value_names_[11]); 1571 EXPECT_NE(value_names_[19], value_names_[14]); 1572 EXPECT_EQ(value_names_[19], value_names_[16]); 1573 EXPECT_EQ(value_names_[19], value_names_[20]); 1574 1575 EXPECT_NE(value_names_[21], value_names_[23]); 1576 1577 EXPECT_NE(value_names_[24], value_names_[26]); 1578 1579 EXPECT_EQ(value_names_[27], value_names_[29]); 1580 } 1581 1582 TEST_F(GlobalValueNumberingTestLoop, Phi) { 1583 static const MIRDef mirs[] = { 1584 DEF_CONST(3, Instruction::CONST, 0u, 1000), 1585 DEF_PHI2(4, 1u, 0u, 6u), // Merge CONST 0u (1000) with the same. 1586 DEF_PHI2(4, 2u, 0u, 7u), // Merge CONST 0u (1000) with the Phi itself. 1587 DEF_PHI2(4, 3u, 0u, 8u), // Merge CONST 0u (1000) and CONST 4u (2000). 1588 DEF_PHI2(4, 4u, 0u, 9u), // Merge CONST 0u (1000) and Phi 3u. 1589 DEF_CONST(4, Instruction::CONST, 5u, 2000), 1590 DEF_MOVE(4, Instruction::MOVE, 6u, 0u), 1591 DEF_MOVE(4, Instruction::MOVE, 7u, 2u), 1592 DEF_MOVE(4, Instruction::MOVE, 8u, 5u), 1593 DEF_MOVE(4, Instruction::MOVE, 9u, 3u), 1594 }; 1595 1596 PrepareMIRs(mirs); 1597 PerformGVN(); 1598 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1599 EXPECT_EQ(value_names_[1], value_names_[0]); 1600 EXPECT_EQ(value_names_[2], value_names_[0]); 1601 1602 EXPECT_NE(value_names_[3], value_names_[0]); 1603 EXPECT_NE(value_names_[3], value_names_[5]); 1604 EXPECT_NE(value_names_[4], value_names_[0]); 1605 EXPECT_NE(value_names_[4], value_names_[5]); 1606 EXPECT_NE(value_names_[4], value_names_[3]); 1607 } 1608 1609 TEST_F(GlobalValueNumberingTestLoop, IFieldLoopVariable) { 1610 static const IFieldDef ifields[] = { 1611 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1612 }; 1613 static const MIRDef mirs[] = { 1614 DEF_CONST(3, Instruction::CONST, 0u, 0), 1615 DEF_IPUT(3, Instruction::IPUT, 0u, 100u, 0u), 1616 DEF_IGET(4, Instruction::IGET, 2u, 100u, 0u), 1617 DEF_BINOP(4, Instruction::ADD_INT, 3u, 2u, 101u), 1618 DEF_IPUT(4, Instruction::IPUT, 3u, 100u, 0u), 1619 }; 1620 1621 PrepareIFields(ifields); 1622 PrepareMIRs(mirs); 1623 PerformGVN(); 1624 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1625 EXPECT_NE(value_names_[2], value_names_[0]); 1626 EXPECT_NE(value_names_[3], value_names_[0]); 1627 EXPECT_NE(value_names_[3], value_names_[2]); 1628 1629 1630 // Set up vreg_to_ssa_map_exit for prologue and loop and set post-processing mode 1631 // as needed for GetStartingVregValueNumber(). 1632 const int32_t prologue_vreg_to_ssa_map_exit[] = { 0 }; 1633 const int32_t loop_vreg_to_ssa_map_exit[] = { 3 }; 1634 PrepareVregToSsaMapExit(3, prologue_vreg_to_ssa_map_exit); 1635 PrepareVregToSsaMapExit(4, loop_vreg_to_ssa_map_exit); 1636 gvn_->StartPostProcessing(); 1637 1638 // Check that vreg 0 has the same value number as the result of IGET 2u. 1639 const LocalValueNumbering* loop = gvn_->GetLvn(4); 1640 EXPECT_EQ(value_names_[2], loop->GetStartingVregValueNumber(0)); 1641 } 1642 1643 TEST_F(GlobalValueNumberingTestCatch, IFields) { 1644 static const IFieldDef ifields[] = { 1645 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1646 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1647 }; 1648 static const MIRDef mirs[] = { 1649 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 200u), 1650 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 201u), 1651 DEF_IGET(3, Instruction::IGET, 2u, 100u, 0u), 1652 DEF_IGET(3, Instruction::IGET, 3u, 200u, 0u), 1653 DEF_IGET(3, Instruction::IGET, 4u, 201u, 0u), 1654 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 201u), // Clobbering catch, 201u escapes. 1655 DEF_IGET(4, Instruction::IGET, 6u, 100u, 0u), // Differs from IGET 2u. 1656 DEF_IPUT(4, Instruction::IPUT, 6u, 100u, 1u), 1657 DEF_IPUT(4, Instruction::IPUT, 6u, 101u, 0u), 1658 DEF_IPUT(4, Instruction::IPUT, 6u, 200u, 0u), 1659 DEF_IGET(5, Instruction::IGET, 10u, 100u, 0u), // Differs from IGETs 2u and 6u. 1660 DEF_IGET(5, Instruction::IGET, 11u, 200u, 0u), // Same as the top. 1661 DEF_IGET(5, Instruction::IGET, 12u, 201u, 0u), // Differs from the top, 201u escaped. 1662 DEF_IPUT(5, Instruction::IPUT, 10u, 100u, 1u), 1663 DEF_IPUT(5, Instruction::IPUT, 10u, 101u, 0u), 1664 DEF_IPUT(5, Instruction::IPUT, 10u, 200u, 0u), 1665 DEF_IGET(6, Instruction::IGET, 16u, 100u, 0u), // Differs from IGETs 2u, 6u and 10u. 1666 DEF_IGET(6, Instruction::IGET, 17u, 100u, 1u), // Same as IGET 16u. 1667 DEF_IGET(6, Instruction::IGET, 18u, 101u, 0u), // Same as IGET 16u. 1668 DEF_IGET(6, Instruction::IGET, 19u, 200u, 0u), // Same as IGET 16u. 1669 }; 1670 1671 PrepareIFields(ifields); 1672 PrepareMIRs(mirs); 1673 PerformGVN(); 1674 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1675 EXPECT_NE(value_names_[2], value_names_[6]); 1676 EXPECT_NE(value_names_[2], value_names_[10]); 1677 EXPECT_NE(value_names_[6], value_names_[10]); 1678 EXPECT_EQ(value_names_[3], value_names_[11]); 1679 EXPECT_NE(value_names_[4], value_names_[12]); 1680 1681 EXPECT_NE(value_names_[2], value_names_[16]); 1682 EXPECT_NE(value_names_[6], value_names_[16]); 1683 EXPECT_NE(value_names_[10], value_names_[16]); 1684 EXPECT_EQ(value_names_[16], value_names_[17]); 1685 EXPECT_EQ(value_names_[16], value_names_[18]); 1686 EXPECT_EQ(value_names_[16], value_names_[19]); 1687 } 1688 1689 TEST_F(GlobalValueNumberingTestCatch, SFields) { 1690 static const SFieldDef sfields[] = { 1691 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1692 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1693 }; 1694 static const MIRDef mirs[] = { 1695 DEF_SGET(3, Instruction::SGET, 0u, 0u), 1696 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 100u), // Clobbering catch. 1697 DEF_SGET(4, Instruction::SGET, 2u, 0u), // Differs from SGET 0u. 1698 DEF_SPUT(4, Instruction::SPUT, 2u, 1u), 1699 DEF_SGET(5, Instruction::SGET, 4u, 0u), // Differs from SGETs 0u and 2u. 1700 DEF_SPUT(5, Instruction::SPUT, 4u, 1u), 1701 DEF_SGET(6, Instruction::SGET, 6u, 0u), // Differs from SGETs 0u, 2u and 4u. 1702 DEF_SGET(6, Instruction::SGET, 7u, 1u), // Same as field #1. 1703 }; 1704 1705 PrepareSFields(sfields); 1706 PrepareMIRs(mirs); 1707 PerformGVN(); 1708 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1709 EXPECT_NE(value_names_[0], value_names_[2]); 1710 EXPECT_NE(value_names_[0], value_names_[4]); 1711 EXPECT_NE(value_names_[2], value_names_[4]); 1712 EXPECT_NE(value_names_[0], value_names_[6]); 1713 EXPECT_NE(value_names_[2], value_names_[6]); 1714 EXPECT_NE(value_names_[4], value_names_[6]); 1715 EXPECT_EQ(value_names_[6], value_names_[7]); 1716 } 1717 1718 TEST_F(GlobalValueNumberingTestCatch, Arrays) { 1719 static const MIRDef mirs[] = { 1720 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u), 1721 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 201u), 1722 DEF_AGET(3, Instruction::AGET, 2u, 100u, 101u), 1723 DEF_AGET(3, Instruction::AGET, 3u, 200u, 202u), 1724 DEF_AGET(3, Instruction::AGET, 4u, 200u, 203u), 1725 DEF_AGET(3, Instruction::AGET, 5u, 201u, 202u), 1726 DEF_AGET(3, Instruction::AGET, 6u, 201u, 203u), 1727 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 201u), // Clobbering catch, 201u escapes. 1728 DEF_AGET(4, Instruction::AGET, 8u, 100u, 101u), // Differs from AGET 2u. 1729 DEF_APUT(4, Instruction::APUT, 8u, 100u, 102u), 1730 DEF_APUT(4, Instruction::APUT, 8u, 200u, 202u), 1731 DEF_APUT(4, Instruction::APUT, 8u, 200u, 203u), 1732 DEF_APUT(4, Instruction::APUT, 8u, 201u, 202u), 1733 DEF_APUT(4, Instruction::APUT, 8u, 201u, 203u), 1734 DEF_AGET(5, Instruction::AGET, 14u, 100u, 101u), // Differs from AGETs 2u and 8u. 1735 DEF_AGET(5, Instruction::AGET, 15u, 200u, 202u), // Same as AGET 3u. 1736 DEF_AGET(5, Instruction::AGET, 16u, 200u, 203u), // Same as AGET 4u. 1737 DEF_AGET(5, Instruction::AGET, 17u, 201u, 202u), // Differs from AGET 5u. 1738 DEF_AGET(5, Instruction::AGET, 18u, 201u, 203u), // Differs from AGET 6u. 1739 DEF_APUT(5, Instruction::APUT, 14u, 100u, 102u), 1740 DEF_APUT(5, Instruction::APUT, 14u, 200u, 202u), 1741 DEF_APUT(5, Instruction::APUT, 14u, 200u, 203u), 1742 DEF_APUT(5, Instruction::APUT, 14u, 201u, 202u), 1743 DEF_APUT(5, Instruction::APUT, 14u, 201u, 203u), 1744 DEF_AGET(6, Instruction::AGET, 24u, 100u, 101u), // Differs from AGETs 2u, 8u and 14u. 1745 DEF_AGET(6, Instruction::AGET, 25u, 100u, 101u), // Same as AGET 24u. 1746 DEF_AGET(6, Instruction::AGET, 26u, 200u, 202u), // Same as AGET 24u. 1747 DEF_AGET(6, Instruction::AGET, 27u, 200u, 203u), // Same as AGET 24u. 1748 DEF_AGET(6, Instruction::AGET, 28u, 201u, 202u), // Same as AGET 24u. 1749 DEF_AGET(6, Instruction::AGET, 29u, 201u, 203u), // Same as AGET 24u. 1750 }; 1751 1752 PrepareMIRs(mirs); 1753 PerformGVN(); 1754 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1755 EXPECT_NE(value_names_[2], value_names_[8]); 1756 EXPECT_NE(value_names_[2], value_names_[14]); 1757 EXPECT_NE(value_names_[8], value_names_[14]); 1758 EXPECT_EQ(value_names_[3], value_names_[15]); 1759 EXPECT_EQ(value_names_[4], value_names_[16]); 1760 EXPECT_NE(value_names_[5], value_names_[17]); 1761 EXPECT_NE(value_names_[6], value_names_[18]); 1762 EXPECT_NE(value_names_[2], value_names_[24]); 1763 EXPECT_NE(value_names_[8], value_names_[24]); 1764 EXPECT_NE(value_names_[14], value_names_[24]); 1765 EXPECT_EQ(value_names_[24], value_names_[25]); 1766 EXPECT_EQ(value_names_[24], value_names_[26]); 1767 EXPECT_EQ(value_names_[24], value_names_[27]); 1768 EXPECT_EQ(value_names_[24], value_names_[28]); 1769 EXPECT_EQ(value_names_[24], value_names_[29]); 1770 } 1771 1772 TEST_F(GlobalValueNumberingTestCatch, Phi) { 1773 static const MIRDef mirs[] = { 1774 DEF_CONST(3, Instruction::CONST, 0u, 1000), 1775 DEF_CONST(3, Instruction::CONST, 1u, 2000), 1776 DEF_MOVE(3, Instruction::MOVE, 2u, 1u), 1777 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 100u), // Clobbering catch. 1778 DEF_CONST(5, Instruction::CONST, 4u, 1000), 1779 DEF_CONST(5, Instruction::CONST, 5u, 3000), 1780 DEF_MOVE(5, Instruction::MOVE, 6u, 5u), 1781 DEF_PHI2(6, 7u, 0u, 4u), 1782 DEF_PHI2(6, 8u, 0u, 5u), 1783 DEF_PHI2(6, 9u, 0u, 6u), 1784 DEF_PHI2(6, 10u, 1u, 4u), 1785 DEF_PHI2(6, 11u, 1u, 5u), 1786 DEF_PHI2(6, 12u, 1u, 6u), 1787 DEF_PHI2(6, 13u, 2u, 4u), 1788 DEF_PHI2(6, 14u, 2u, 5u), 1789 DEF_PHI2(6, 15u, 2u, 6u), 1790 }; 1791 PrepareMIRs(mirs); 1792 PerformGVN(); 1793 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1794 ASSERT_EQ(value_names_[4], value_names_[0]); // Both CONSTs are 1000. 1795 EXPECT_EQ(value_names_[7], value_names_[0]); // Merging CONST 0u and CONST 4u, both 1000. 1796 EXPECT_NE(value_names_[8], value_names_[0]); 1797 EXPECT_NE(value_names_[8], value_names_[5]); 1798 EXPECT_EQ(value_names_[9], value_names_[8]); 1799 EXPECT_NE(value_names_[10], value_names_[1]); 1800 EXPECT_NE(value_names_[10], value_names_[4]); 1801 EXPECT_NE(value_names_[10], value_names_[8]); 1802 EXPECT_NE(value_names_[11], value_names_[1]); 1803 EXPECT_NE(value_names_[11], value_names_[5]); 1804 EXPECT_NE(value_names_[11], value_names_[8]); 1805 EXPECT_NE(value_names_[11], value_names_[10]); 1806 EXPECT_EQ(value_names_[12], value_names_[11]); 1807 EXPECT_EQ(value_names_[13], value_names_[10]); 1808 EXPECT_EQ(value_names_[14], value_names_[11]); 1809 EXPECT_EQ(value_names_[15], value_names_[11]); 1810 } 1811 1812 TEST_F(GlobalValueNumberingTest, NullCheckIFields) { 1813 static const IFieldDef ifields[] = { 1814 { 0u, 1u, 0u, false, kDexMemAccessObject }, // Object. 1815 { 1u, 1u, 1u, false, kDexMemAccessObject }, // Object. 1816 }; 1817 static const BBDef bbs[] = { 1818 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 1819 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 1820 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 1821 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // 4 is fall-through, 5 is taken. 1822 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)), 1823 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)), 1824 }; 1825 static const MIRDef mirs[] = { 1826 DEF_IGET(3, Instruction::IGET_OBJECT, 0u, 100u, 0u), 1827 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 100u, 1u), 1828 DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 101u, 0u), 1829 DEF_IFZ(3, Instruction::IF_NEZ, 0u), // Null-check for field #0 for taken. 1830 DEF_UNIQUE_REF(4, Instruction::NEW_ARRAY, 4u), 1831 DEF_IPUT(4, Instruction::IPUT_OBJECT, 4u, 100u, 0u), 1832 DEF_IPUT(4, Instruction::IPUT_OBJECT, 4u, 100u, 1u), 1833 DEF_IPUT(4, Instruction::IPUT_OBJECT, 4u, 101u, 0u), 1834 DEF_IGET(5, Instruction::IGET_OBJECT, 8u, 100u, 0u), // 100u/#0, IF_NEZ/NEW_ARRAY. 1835 DEF_IGET(5, Instruction::IGET_OBJECT, 9u, 100u, 1u), // 100u/#1, -/NEW_ARRAY. 1836 DEF_IGET(5, Instruction::IGET_OBJECT, 10u, 101u, 0u), // 101u/#0, -/NEW_ARRAY. 1837 DEF_CONST(5, Instruction::CONST, 11u, 0), 1838 DEF_AGET(5, Instruction::AGET, 12u, 8u, 11u), // Null-check eliminated. 1839 DEF_AGET(5, Instruction::AGET, 13u, 9u, 11u), // Null-check kept. 1840 DEF_AGET(5, Instruction::AGET, 14u, 10u, 11u), // Null-check kept. 1841 }; 1842 static const bool expected_ignore_null_check[] = { 1843 false, true, false, false, // BB #3; unimportant. 1844 false, true, true, true, // BB #4; unimportant. 1845 true, true, true, false, true, false, false, // BB #5; only the last three are important. 1846 }; 1847 1848 PrepareIFields(ifields); 1849 PrepareBasicBlocks(bbs); 1850 PrepareMIRs(mirs); 1851 PerformGVN(); 1852 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1853 PerformGVNCodeModifications(); 1854 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 1855 for (size_t i = 0u; i != arraysize(mirs); ++i) { 1856 EXPECT_EQ(expected_ignore_null_check[i], 1857 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 1858 } 1859 } 1860 1861 TEST_F(GlobalValueNumberingTest, NullCheckSFields) { 1862 static const SFieldDef sfields[] = { 1863 { 0u, 1u, 0u, false, kDexMemAccessObject }, 1864 { 1u, 1u, 1u, false, kDexMemAccessObject }, 1865 }; 1866 static const BBDef bbs[] = { 1867 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 1868 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 1869 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 1870 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // 4 is fall-through, 5 is taken. 1871 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)), 1872 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)), 1873 }; 1874 static const MIRDef mirs[] = { 1875 DEF_SGET(3, Instruction::SGET_OBJECT, 0u, 0u), 1876 DEF_SGET(3, Instruction::SGET_OBJECT, 1u, 1u), 1877 DEF_IFZ(3, Instruction::IF_NEZ, 0u), // Null-check for field #0 for taken. 1878 DEF_UNIQUE_REF(4, Instruction::NEW_ARRAY, 3u), 1879 DEF_SPUT(4, Instruction::SPUT_OBJECT, 3u, 0u), 1880 DEF_SPUT(4, Instruction::SPUT_OBJECT, 3u, 1u), 1881 DEF_SGET(5, Instruction::SGET_OBJECT, 6u, 0u), // Field #0 is null-checked, IF_NEZ/NEW_ARRAY. 1882 DEF_SGET(5, Instruction::SGET_OBJECT, 7u, 1u), // Field #1 is not null-checked, -/NEW_ARRAY. 1883 DEF_CONST(5, Instruction::CONST, 8u, 0), 1884 DEF_AGET(5, Instruction::AGET, 9u, 6u, 8u), // Null-check eliminated. 1885 DEF_AGET(5, Instruction::AGET, 10u, 7u, 8u), // Null-check kept. 1886 }; 1887 static const bool expected_ignore_null_check[] = { 1888 false, false, false, false, false, false, false, false, false, true, false 1889 }; 1890 1891 PrepareSFields(sfields); 1892 PrepareBasicBlocks(bbs); 1893 PrepareMIRs(mirs); 1894 PerformGVN(); 1895 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1896 PerformGVNCodeModifications(); 1897 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 1898 for (size_t i = 0u; i != arraysize(mirs); ++i) { 1899 EXPECT_EQ(expected_ignore_null_check[i], 1900 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 1901 } 1902 } 1903 1904 TEST_F(GlobalValueNumberingTest, NullCheckArrays) { 1905 static const BBDef bbs[] = { 1906 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 1907 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 1908 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 1909 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // 4 is fall-through, 5 is taken. 1910 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)), 1911 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)), 1912 }; 1913 static const MIRDef mirs[] = { 1914 DEF_AGET(3, Instruction::AGET_OBJECT, 0u, 100u, 102u), 1915 DEF_AGET(3, Instruction::AGET_OBJECT, 1u, 100u, 103u), 1916 DEF_AGET(3, Instruction::AGET_OBJECT, 2u, 101u, 102u), 1917 DEF_IFZ(3, Instruction::IF_NEZ, 0u), // Null-check for field #0 for taken. 1918 DEF_UNIQUE_REF(4, Instruction::NEW_ARRAY, 4u), 1919 DEF_APUT(4, Instruction::APUT_OBJECT, 4u, 100u, 102u), 1920 DEF_APUT(4, Instruction::APUT_OBJECT, 4u, 100u, 103u), 1921 DEF_APUT(4, Instruction::APUT_OBJECT, 4u, 101u, 102u), 1922 DEF_AGET(5, Instruction::AGET_OBJECT, 8u, 100u, 102u), // Null-checked, IF_NEZ/NEW_ARRAY. 1923 DEF_AGET(5, Instruction::AGET_OBJECT, 9u, 100u, 103u), // Not null-checked, -/NEW_ARRAY. 1924 DEF_AGET(5, Instruction::AGET_OBJECT, 10u, 101u, 102u), // Not null-checked, -/NEW_ARRAY. 1925 DEF_CONST(5, Instruction::CONST, 11u, 0), 1926 DEF_AGET(5, Instruction::AGET, 12u, 8u, 11u), // Null-check eliminated. 1927 DEF_AGET(5, Instruction::AGET, 13u, 9u, 11u), // Null-check kept. 1928 DEF_AGET(5, Instruction::AGET, 14u, 10u, 11u), // Null-check kept. 1929 }; 1930 static const bool expected_ignore_null_check[] = { 1931 false, true, false, false, // BB #3; unimportant. 1932 false, true, true, true, // BB #4; unimportant. 1933 true, true, true, false, true, false, false, // BB #5; only the last three are important. 1934 }; 1935 1936 PrepareBasicBlocks(bbs); 1937 PrepareMIRs(mirs); 1938 PerformGVN(); 1939 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1940 PerformGVNCodeModifications(); 1941 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 1942 for (size_t i = 0u; i != arraysize(mirs); ++i) { 1943 EXPECT_EQ(expected_ignore_null_check[i], 1944 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 1945 } 1946 } 1947 1948 TEST_F(GlobalValueNumberingTestDiamond, RangeCheckArrays) { 1949 // NOTE: We don't merge range checks when we merge value names for Phis or memory locations. 1950 static const MIRDef mirs[] = { 1951 DEF_AGET(4, Instruction::AGET, 0u, 100u, 101u), 1952 DEF_AGET(5, Instruction::AGET, 1u, 100u, 101u), 1953 DEF_APUT(6, Instruction::APUT, 2u, 100u, 101u), 1954 1955 DEF_AGET(4, Instruction::AGET, 3u, 200u, 201u), 1956 DEF_AGET(5, Instruction::AGET, 4u, 200u, 202u), 1957 DEF_APUT(6, Instruction::APUT, 5u, 200u, 201u), 1958 1959 DEF_AGET(4, Instruction::AGET, 6u, 300u, 302u), 1960 DEF_AGET(5, Instruction::AGET, 7u, 301u, 302u), 1961 DEF_APUT(6, Instruction::APUT, 8u, 300u, 302u), 1962 }; 1963 static const bool expected_ignore_null_check[] = { 1964 false, false, true, 1965 false, false, true, 1966 false, false, false, 1967 }; 1968 static const bool expected_ignore_range_check[] = { 1969 false, false, true, 1970 false, false, false, 1971 false, false, false, 1972 }; 1973 1974 PrepareMIRs(mirs); 1975 PerformGVN(); 1976 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1977 PerformGVNCodeModifications(); 1978 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_); 1979 ASSERT_EQ(arraysize(expected_ignore_range_check), mir_count_); 1980 for (size_t i = 0u; i != arraysize(mirs); ++i) { 1981 EXPECT_EQ(expected_ignore_null_check[i], 1982 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 1983 EXPECT_EQ(expected_ignore_range_check[i], 1984 (mirs_[i].optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0) << i; 1985 } 1986 } 1987 1988 TEST_F(GlobalValueNumberingTestDiamond, MergeSameValueInDifferentMemoryLocations) { 1989 static const IFieldDef ifields[] = { 1990 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1991 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1992 }; 1993 static const SFieldDef sfields[] = { 1994 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1995 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1996 }; 1997 static const MIRDef mirs[] = { 1998 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 100u), 1999 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u), 2000 DEF_CONST(4, Instruction::CONST, 2u, 1000), 2001 DEF_IPUT(4, Instruction::IPUT, 2u, 100u, 0u), 2002 DEF_IPUT(4, Instruction::IPUT, 2u, 100u, 1u), 2003 DEF_IPUT(4, Instruction::IPUT, 2u, 101u, 0u), 2004 DEF_APUT(4, Instruction::APUT, 2u, 200u, 202u), 2005 DEF_APUT(4, Instruction::APUT, 2u, 200u, 203u), 2006 DEF_APUT(4, Instruction::APUT, 2u, 201u, 202u), 2007 DEF_APUT(4, Instruction::APUT, 2u, 201u, 203u), 2008 DEF_SPUT(4, Instruction::SPUT, 2u, 0u), 2009 DEF_SPUT(4, Instruction::SPUT, 2u, 1u), 2010 DEF_CONST(5, Instruction::CONST, 12u, 2000), 2011 DEF_IPUT(5, Instruction::IPUT, 12u, 100u, 0u), 2012 DEF_IPUT(5, Instruction::IPUT, 12u, 100u, 1u), 2013 DEF_IPUT(5, Instruction::IPUT, 12u, 101u, 0u), 2014 DEF_APUT(5, Instruction::APUT, 12u, 200u, 202u), 2015 DEF_APUT(5, Instruction::APUT, 12u, 200u, 203u), 2016 DEF_APUT(5, Instruction::APUT, 12u, 201u, 202u), 2017 DEF_APUT(5, Instruction::APUT, 12u, 201u, 203u), 2018 DEF_SPUT(5, Instruction::SPUT, 12u, 0u), 2019 DEF_SPUT(5, Instruction::SPUT, 12u, 1u), 2020 DEF_PHI2(6, 22u, 2u, 12u), 2021 DEF_IGET(6, Instruction::IGET, 23u, 100u, 0u), 2022 DEF_IGET(6, Instruction::IGET, 24u, 100u, 1u), 2023 DEF_IGET(6, Instruction::IGET, 25u, 101u, 0u), 2024 DEF_AGET(6, Instruction::AGET, 26u, 200u, 202u), 2025 DEF_AGET(6, Instruction::AGET, 27u, 200u, 203u), 2026 DEF_AGET(6, Instruction::AGET, 28u, 201u, 202u), 2027 DEF_AGET(6, Instruction::AGET, 29u, 201u, 203u), 2028 DEF_SGET(6, Instruction::SGET, 30u, 0u), 2029 DEF_SGET(6, Instruction::SGET, 31u, 1u), 2030 }; 2031 PrepareIFields(ifields); 2032 PrepareSFields(sfields); 2033 PrepareMIRs(mirs); 2034 PerformGVN(); 2035 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2036 EXPECT_NE(value_names_[2], value_names_[12]); 2037 EXPECT_NE(value_names_[2], value_names_[22]); 2038 EXPECT_NE(value_names_[12], value_names_[22]); 2039 for (size_t i = 23; i != arraysize(mirs); ++i) { 2040 EXPECT_EQ(value_names_[22], value_names_[i]) << i; 2041 } 2042 } 2043 2044 TEST_F(GlobalValueNumberingTest, InfiniteLocationLoop) { 2045 // This is a pattern that lead to an infinite loop during the GVN development. This has been 2046 // fixed by rewriting the merging of AliasingValues to merge only locations read from or 2047 // written to in each incoming LVN rather than merging all locations read from or written to 2048 // in any incoming LVN. It also showed up only when the GVN used the DFS ordering instead of 2049 // the "topological" ordering but, since the "topological" ordering is not really topological 2050 // when there are cycles and an optimizing Java compiler (or a tool like proguard) could 2051 // theoretically create any sort of flow graph, this could have shown up in real code. 2052 // 2053 // While we were merging all the locations: 2054 // The first time the Phi evaluates to the same value name as CONST 0u. After the second 2055 // evaluation, when the BB #9 has been processed, the Phi receives its own value name. 2056 // However, the index from the first evaluation keeps disappearing and reappearing in the 2057 // LVN's aliasing_array_value_map_'s load_value_map for BBs #9, #4, #5, #7 because of the 2058 // DFS ordering of LVN evaluation. 2059 static const IFieldDef ifields[] = { 2060 { 0u, 1u, 0u, false, kDexMemAccessObject }, 2061 }; 2062 static const BBDef bbs[] = { 2063 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 2064 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 2065 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(4)), 2066 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 2067 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 2), DEF_PRED2(3, 9)), 2068 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED1(4)), 2069 DEF_BB(kDalvikByteCode, DEF_SUCC1(9), DEF_PRED1(5)), 2070 DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED1(5)), 2071 DEF_BB(kDalvikByteCode, DEF_SUCC1(9), DEF_PRED1(7)), 2072 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED3(6, 7, 8)), 2073 }; 2074 static const MIRDef mirs[] = { 2075 DEF_CONST(3, Instruction::CONST, 0u, 0), 2076 DEF_PHI2(4, 1u, 0u, 10u), 2077 DEF_INVOKE1(6, Instruction::INVOKE_STATIC, 100u), 2078 DEF_IGET(6, Instruction::IGET_OBJECT, 3u, 100u, 0u), 2079 DEF_CONST(6, Instruction::CONST, 4u, 1000), 2080 DEF_APUT(6, Instruction::APUT, 4u, 3u, 1u), // Index is Phi 1u. 2081 DEF_INVOKE1(8, Instruction::INVOKE_STATIC, 100u), 2082 DEF_IGET(8, Instruction::IGET_OBJECT, 7u, 100u, 0u), 2083 DEF_CONST(8, Instruction::CONST, 8u, 2000), 2084 DEF_APUT(8, Instruction::APUT, 9u, 7u, 1u), // Index is Phi 1u. 2085 DEF_CONST(9, Instruction::CONST, 10u, 3000), 2086 }; 2087 PrepareIFields(ifields); 2088 PrepareBasicBlocks(bbs); 2089 PrepareMIRs(mirs); 2090 // Using DFS order for this test. The GVN result should not depend on the used ordering 2091 // once the GVN actually converges. But creating a test for this convergence issue with 2092 // the topological ordering could be a very challenging task. 2093 PerformPreOrderDfsGVN(); 2094 } 2095 2096 TEST_F(GlobalValueNumberingTestTwoConsecutiveLoops, IFieldAndPhi) { 2097 static const IFieldDef ifields[] = { 2098 { 0u, 1u, 0u, false, kDexMemAccessObject }, 2099 }; 2100 static const MIRDef mirs[] = { 2101 DEF_MOVE(3, Instruction::MOVE_OBJECT, 0u, 100u), 2102 DEF_IPUT(3, Instruction::IPUT_OBJECT, 0u, 200u, 0u), 2103 DEF_PHI2(4, 2u, 0u, 3u), 2104 DEF_MOVE(5, Instruction::MOVE_OBJECT, 3u, 300u), 2105 DEF_IPUT(5, Instruction::IPUT_OBJECT, 3u, 200u, 0u), 2106 DEF_MOVE(6, Instruction::MOVE_OBJECT, 5u, 2u), 2107 DEF_IGET(6, Instruction::IGET_OBJECT, 6u, 200u, 0u), 2108 DEF_MOVE(7, Instruction::MOVE_OBJECT, 7u, 5u), 2109 DEF_IGET(7, Instruction::IGET_OBJECT, 8u, 200u, 0u), 2110 DEF_MOVE(8, Instruction::MOVE_OBJECT, 9u, 5u), 2111 DEF_IGET(8, Instruction::IGET_OBJECT, 10u, 200u, 0u), 2112 DEF_MOVE(9, Instruction::MOVE_OBJECT, 11u, 5u), 2113 DEF_IGET(9, Instruction::IGET_OBJECT, 12u, 200u, 0u), 2114 }; 2115 2116 PrepareIFields(ifields); 2117 PrepareMIRs(mirs); 2118 PerformGVN(); 2119 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2120 EXPECT_NE(value_names_[0], value_names_[3]); 2121 EXPECT_NE(value_names_[0], value_names_[2]); 2122 EXPECT_NE(value_names_[3], value_names_[2]); 2123 EXPECT_EQ(value_names_[2], value_names_[5]); 2124 EXPECT_EQ(value_names_[5], value_names_[6]); 2125 EXPECT_EQ(value_names_[5], value_names_[7]); 2126 EXPECT_EQ(value_names_[5], value_names_[8]); 2127 EXPECT_EQ(value_names_[5], value_names_[9]); 2128 EXPECT_EQ(value_names_[5], value_names_[10]); 2129 EXPECT_EQ(value_names_[5], value_names_[11]); 2130 EXPECT_EQ(value_names_[5], value_names_[12]); 2131 } 2132 2133 TEST_F(GlobalValueNumberingTestTwoConsecutiveLoops, NullCheck) { 2134 static const IFieldDef ifields[] = { 2135 { 0u, 1u, 0u, false, kDexMemAccessObject }, 2136 }; 2137 static const SFieldDef sfields[] = { 2138 { 0u, 1u, 0u, false, kDexMemAccessObject }, 2139 }; 2140 static const MIRDef mirs[] = { 2141 DEF_MOVE(3, Instruction::MOVE_OBJECT, 0u, 100u), 2142 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 200u, 0u), 2143 DEF_SGET(3, Instruction::SGET_OBJECT, 2u, 0u), 2144 DEF_AGET(3, Instruction::AGET_OBJECT, 3u, 300u, 201u), 2145 DEF_PHI2(4, 4u, 0u, 8u), 2146 DEF_IGET(5, Instruction::IGET_OBJECT, 5u, 200u, 0u), 2147 DEF_SGET(5, Instruction::SGET_OBJECT, 6u, 0u), 2148 DEF_AGET(5, Instruction::AGET_OBJECT, 7u, 300u, 201u), 2149 DEF_MOVE(5, Instruction::MOVE_OBJECT, 8u, 400u), 2150 DEF_IPUT(5, Instruction::IPUT_OBJECT, 4u, 200u, 0u), // PUT the Phi 4u. 2151 DEF_SPUT(5, Instruction::SPUT_OBJECT, 4u, 0u), // PUT the Phi 4u. 2152 DEF_APUT(5, Instruction::APUT_OBJECT, 4u, 300u, 201u), // PUT the Phi 4u. 2153 DEF_MOVE(6, Instruction::MOVE_OBJECT, 12u, 4u), 2154 DEF_IGET(6, Instruction::IGET_OBJECT, 13u, 200u, 0u), 2155 DEF_SGET(6, Instruction::SGET_OBJECT, 14u, 0u), 2156 DEF_AGET(6, Instruction::AGET_OBJECT, 15u, 300u, 201u), 2157 DEF_AGET(6, Instruction::AGET_OBJECT, 16u, 12u, 600u), 2158 DEF_AGET(6, Instruction::AGET_OBJECT, 17u, 13u, 600u), 2159 DEF_AGET(6, Instruction::AGET_OBJECT, 18u, 14u, 600u), 2160 DEF_AGET(6, Instruction::AGET_OBJECT, 19u, 15u, 600u), 2161 DEF_MOVE(8, Instruction::MOVE_OBJECT, 20u, 12u), 2162 DEF_IGET(8, Instruction::IGET_OBJECT, 21u, 200u, 0u), 2163 DEF_SGET(8, Instruction::SGET_OBJECT, 22u, 0u), 2164 DEF_AGET(8, Instruction::AGET_OBJECT, 23u, 300u, 201u), 2165 DEF_AGET(8, Instruction::AGET_OBJECT, 24u, 12u, 600u), 2166 DEF_AGET(8, Instruction::AGET_OBJECT, 25u, 13u, 600u), 2167 DEF_AGET(8, Instruction::AGET_OBJECT, 26u, 14u, 600u), 2168 DEF_AGET(8, Instruction::AGET_OBJECT, 27u, 15u, 600u), 2169 DEF_MOVE(9, Instruction::MOVE_OBJECT, 28u, 12u), 2170 DEF_IGET(9, Instruction::IGET_OBJECT, 29u, 200u, 0u), 2171 DEF_SGET(9, Instruction::SGET_OBJECT, 30u, 0u), 2172 DEF_AGET(9, Instruction::AGET_OBJECT, 31u, 300u, 201u), 2173 DEF_AGET(9, Instruction::AGET_OBJECT, 32u, 12u, 600u), 2174 DEF_AGET(9, Instruction::AGET_OBJECT, 33u, 13u, 600u), 2175 DEF_AGET(9, Instruction::AGET_OBJECT, 34u, 14u, 600u), 2176 DEF_AGET(9, Instruction::AGET_OBJECT, 35u, 15u, 600u), 2177 }; 2178 static const bool expected_ignore_null_check[] = { 2179 false, false, false, false, // BB #3. 2180 false, true, false, true, false, true, false, true, // BBs #4 and #5. 2181 false, true, false, true, false, false, false, false, // BB #6. 2182 false, true, false, true, true, true, true, true, // BB #7. 2183 false, true, false, true, true, true, true, true, // BB #8. 2184 }; 2185 static const bool expected_ignore_range_check[] = { 2186 false, false, false, false, // BB #3. 2187 false, false, false, true, false, false, false, true, // BBs #4 and #5. 2188 false, false, false, true, false, false, false, false, // BB #6. 2189 false, false, false, true, true, true, true, true, // BB #7. 2190 false, false, false, true, true, true, true, true, // BB #8. 2191 }; 2192 2193 PrepareIFields(ifields); 2194 PrepareSFields(sfields); 2195 PrepareMIRs(mirs); 2196 PerformGVN(); 2197 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2198 EXPECT_NE(value_names_[0], value_names_[4]); 2199 EXPECT_NE(value_names_[1], value_names_[5]); 2200 EXPECT_NE(value_names_[2], value_names_[6]); 2201 EXPECT_NE(value_names_[3], value_names_[7]); 2202 EXPECT_NE(value_names_[4], value_names_[8]); 2203 EXPECT_EQ(value_names_[4], value_names_[12]); 2204 EXPECT_EQ(value_names_[5], value_names_[13]); 2205 EXPECT_EQ(value_names_[6], value_names_[14]); 2206 EXPECT_EQ(value_names_[7], value_names_[15]); 2207 EXPECT_EQ(value_names_[12], value_names_[20]); 2208 EXPECT_EQ(value_names_[13], value_names_[21]); 2209 EXPECT_EQ(value_names_[14], value_names_[22]); 2210 EXPECT_EQ(value_names_[15], value_names_[23]); 2211 EXPECT_EQ(value_names_[12], value_names_[28]); 2212 EXPECT_EQ(value_names_[13], value_names_[29]); 2213 EXPECT_EQ(value_names_[14], value_names_[30]); 2214 EXPECT_EQ(value_names_[15], value_names_[31]); 2215 PerformGVNCodeModifications(); 2216 for (size_t i = 0u; i != arraysize(mirs); ++i) { 2217 EXPECT_EQ(expected_ignore_null_check[i], 2218 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i; 2219 EXPECT_EQ(expected_ignore_range_check[i], 2220 (mirs_[i].optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0) << i; 2221 } 2222 } 2223 2224 TEST_F(GlobalValueNumberingTestTwoNestedLoops, IFieldAndPhi) { 2225 static const IFieldDef ifields[] = { 2226 { 0u, 1u, 0u, false, kDexMemAccessObject }, 2227 }; 2228 static const MIRDef mirs[] = { 2229 DEF_MOVE(3, Instruction::MOVE_OBJECT, 0u, 100u), 2230 DEF_IPUT(3, Instruction::IPUT_OBJECT, 0u, 200u, 0u), 2231 DEF_PHI2(4, 2u, 0u, 11u), 2232 DEF_MOVE(4, Instruction::MOVE_OBJECT, 3u, 2u), 2233 DEF_IGET(4, Instruction::IGET_OBJECT, 4u, 200u, 0u), 2234 DEF_MOVE(5, Instruction::MOVE_OBJECT, 5u, 3u), 2235 DEF_IGET(5, Instruction::IGET_OBJECT, 6u, 200u, 0u), 2236 DEF_MOVE(6, Instruction::MOVE_OBJECT, 7u, 3u), 2237 DEF_IGET(6, Instruction::IGET_OBJECT, 8u, 200u, 0u), 2238 DEF_MOVE(7, Instruction::MOVE_OBJECT, 9u, 3u), 2239 DEF_IGET(7, Instruction::IGET_OBJECT, 10u, 200u, 0u), 2240 DEF_MOVE(7, Instruction::MOVE_OBJECT, 11u, 300u), 2241 DEF_IPUT(7, Instruction::IPUT_OBJECT, 11u, 200u, 0u), 2242 DEF_MOVE(8, Instruction::MOVE_OBJECT, 13u, 3u), 2243 DEF_IGET(8, Instruction::IGET_OBJECT, 14u, 200u, 0u), 2244 }; 2245 2246 PrepareIFields(ifields); 2247 PrepareMIRs(mirs); 2248 PerformGVN(); 2249 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2250 EXPECT_NE(value_names_[0], value_names_[11]); 2251 EXPECT_NE(value_names_[0], value_names_[2]); 2252 EXPECT_NE(value_names_[11], value_names_[2]); 2253 EXPECT_EQ(value_names_[2], value_names_[3]); 2254 EXPECT_EQ(value_names_[3], value_names_[4]); 2255 EXPECT_EQ(value_names_[3], value_names_[5]); 2256 EXPECT_EQ(value_names_[3], value_names_[6]); 2257 EXPECT_EQ(value_names_[3], value_names_[7]); 2258 EXPECT_EQ(value_names_[3], value_names_[8]); 2259 EXPECT_EQ(value_names_[3], value_names_[9]); 2260 EXPECT_EQ(value_names_[3], value_names_[10]); 2261 EXPECT_EQ(value_names_[3], value_names_[13]); 2262 EXPECT_EQ(value_names_[3], value_names_[14]); 2263 } 2264 2265 TEST_F(GlobalValueNumberingTest, NormalPathToCatchEntry) { 2266 // When there's an empty catch block, all the exception paths lead to the next block in 2267 // the normal path and we can also have normal "taken" or "fall-through" branches to that 2268 // path. Check that LocalValueNumbering::PruneNonAliasingRefsForCatch() can handle it. 2269 static const BBDef bbs[] = { 2270 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 2271 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 2272 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 2273 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 2274 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)), 2275 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)), 2276 }; 2277 static const MIRDef mirs[] = { 2278 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 100u), 2279 }; 2280 PrepareBasicBlocks(bbs); 2281 BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u); 2282 catch_handler->catch_entry = true; 2283 // Add successor block info to the check block. 2284 BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u); 2285 check_bb->successor_block_list_type = kCatch; 2286 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*> 2287 (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor)); 2288 successor_block_info->block = catch_handler->id; 2289 check_bb->successor_blocks.push_back(successor_block_info); 2290 BasicBlock* merge_block = cu_.mir_graph->GetBasicBlock(4u); 2291 std::swap(merge_block->taken, merge_block->fall_through); 2292 PrepareMIRs(mirs); 2293 PerformGVN(); 2294 } 2295 2296 TEST_F(GlobalValueNumberingTestDiamond, DivZeroCheckDiamond) { 2297 static const MIRDef mirs[] = { 2298 DEF_BINOP(3u, Instruction::DIV_INT, 1u, 20u, 21u), 2299 DEF_BINOP(3u, Instruction::DIV_INT, 2u, 24u, 21u), 2300 DEF_BINOP(3u, Instruction::DIV_INT, 3u, 20u, 23u), 2301 DEF_BINOP(4u, Instruction::DIV_INT, 4u, 24u, 22u), 2302 DEF_BINOP(4u, Instruction::DIV_INT, 9u, 24u, 25u), 2303 DEF_BINOP(5u, Instruction::DIV_INT, 5u, 24u, 21u), 2304 DEF_BINOP(5u, Instruction::DIV_INT, 10u, 24u, 26u), 2305 DEF_PHI2(6u, 27u, 25u, 26u), 2306 DEF_BINOP(6u, Instruction::DIV_INT, 12u, 20u, 27u), 2307 DEF_BINOP(6u, Instruction::DIV_INT, 6u, 24u, 21u), 2308 DEF_BINOP(6u, Instruction::DIV_INT, 7u, 20u, 23u), 2309 DEF_BINOP(6u, Instruction::DIV_INT, 8u, 20u, 22u), 2310 }; 2311 2312 static const bool expected_ignore_div_zero_check[] = { 2313 false, // New divisor seen. 2314 true, // Eliminated since it has first divisor as first one. 2315 false, // New divisor seen. 2316 false, // New divisor seen. 2317 false, // New divisor seen. 2318 true, // Eliminated in dominating block. 2319 false, // New divisor seen. 2320 false, // Phi node. 2321 true, // Eliminated on both sides of diamond and merged via phi. 2322 true, // Eliminated in dominating block. 2323 true, // Eliminated in dominating block. 2324 false, // Only eliminated on one path of diamond. 2325 }; 2326 2327 PrepareMIRs(mirs); 2328 PerformGVN(); 2329 PerformGVNCodeModifications(); 2330 ASSERT_EQ(arraysize(expected_ignore_div_zero_check), mir_count_); 2331 for (size_t i = 0u; i != mir_count_; ++i) { 2332 int expected = expected_ignore_div_zero_check[i] ? MIR_IGNORE_DIV_ZERO_CHECK : 0u; 2333 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 2334 } 2335 } 2336 2337 TEST_F(GlobalValueNumberingTestDiamond, CheckCastDiamond) { 2338 static const MIRDef mirs[] = { 2339 DEF_UNOP(3u, Instruction::INSTANCE_OF, 0u, 100u), 2340 DEF_UNOP(3u, Instruction::INSTANCE_OF, 1u, 200u), 2341 DEF_IFZ(3u, Instruction::IF_NEZ, 0u), 2342 DEF_INVOKE1(4u, Instruction::CHECK_CAST, 100u), 2343 DEF_INVOKE1(5u, Instruction::CHECK_CAST, 100u), 2344 DEF_INVOKE1(5u, Instruction::CHECK_CAST, 200u), 2345 DEF_INVOKE1(5u, Instruction::CHECK_CAST, 100u), 2346 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 100u), 2347 }; 2348 2349 static const bool expected_ignore_check_cast[] = { 2350 false, // instance-of 2351 false, // instance-of 2352 false, // if-nez 2353 false, // Not eliminated, fall-through branch. 2354 true, // Eliminated. 2355 false, // Not eliminated, different value. 2356 false, // Not eliminated, different type. 2357 false, // Not eliminated, bottom block. 2358 }; 2359 2360 PrepareMIRs(mirs); 2361 mirs_[0].dalvikInsn.vC = 1234; // type for instance-of 2362 mirs_[1].dalvikInsn.vC = 1234; // type for instance-of 2363 mirs_[3].dalvikInsn.vB = 1234; // type for check-cast 2364 mirs_[4].dalvikInsn.vB = 1234; // type for check-cast 2365 mirs_[5].dalvikInsn.vB = 1234; // type for check-cast 2366 mirs_[6].dalvikInsn.vB = 4321; // type for check-cast 2367 mirs_[7].dalvikInsn.vB = 1234; // type for check-cast 2368 PerformGVN(); 2369 PerformGVNCodeModifications(); 2370 ASSERT_EQ(arraysize(expected_ignore_check_cast), mir_count_); 2371 for (size_t i = 0u; i != mir_count_; ++i) { 2372 int expected = expected_ignore_check_cast[i] ? MIR_IGNORE_CHECK_CAST : 0u; 2373 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 2374 } 2375 } 2376 2377 TEST_F(GlobalValueNumberingTest, CheckCastDominators) { 2378 const BBDef bbs[] = { 2379 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 2380 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 2381 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(7)), 2382 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // Block #3, top of the diamond. 2383 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(3)), // Block #4, left side. 2384 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #5, right side. 2385 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(5)), // Block #6, right side. 2386 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 6)), // Block #7, bottom. 2387 }; 2388 static const MIRDef mirs[] = { 2389 DEF_UNOP(3u, Instruction::INSTANCE_OF, 0u, 100u), 2390 DEF_UNOP(3u, Instruction::INSTANCE_OF, 1u, 200u), 2391 DEF_IFZ(3u, Instruction::IF_NEZ, 0u), 2392 DEF_INVOKE1(4u, Instruction::CHECK_CAST, 100u), 2393 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 100u), 2394 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 200u), 2395 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 100u), 2396 DEF_INVOKE1(7u, Instruction::CHECK_CAST, 100u), 2397 }; 2398 2399 static const bool expected_ignore_check_cast[] = { 2400 false, // instance-of 2401 false, // instance-of 2402 false, // if-nez 2403 false, // Not eliminated, fall-through branch. 2404 true, // Eliminated. 2405 false, // Not eliminated, different value. 2406 false, // Not eliminated, different type. 2407 false, // Not eliminated, bottom block. 2408 }; 2409 2410 PrepareBasicBlocks(bbs); 2411 PrepareMIRs(mirs); 2412 mirs_[0].dalvikInsn.vC = 1234; // type for instance-of 2413 mirs_[1].dalvikInsn.vC = 1234; // type for instance-of 2414 mirs_[3].dalvikInsn.vB = 1234; // type for check-cast 2415 mirs_[4].dalvikInsn.vB = 1234; // type for check-cast 2416 mirs_[5].dalvikInsn.vB = 1234; // type for check-cast 2417 mirs_[6].dalvikInsn.vB = 4321; // type for check-cast 2418 mirs_[7].dalvikInsn.vB = 1234; // type for check-cast 2419 PerformGVN(); 2420 PerformGVNCodeModifications(); 2421 ASSERT_EQ(arraysize(expected_ignore_check_cast), mir_count_); 2422 for (size_t i = 0u; i != mir_count_; ++i) { 2423 int expected = expected_ignore_check_cast[i] ? MIR_IGNORE_CHECK_CAST : 0u; 2424 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 2425 } 2426 } 2427 2428 } // namespace art 2429
