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