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