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