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 "global_value_numbering.h" 19 #include "local_value_numbering.h" 20 #include "gtest/gtest.h" 21 22 namespace art { 23 24 class LocalValueNumberingTest : public testing::Test { 25 protected: 26 struct IFieldDef { 27 uint16_t field_idx; 28 uintptr_t declaring_dex_file; 29 uint16_t declaring_field_idx; 30 bool is_volatile; 31 }; 32 33 struct SFieldDef { 34 uint16_t field_idx; 35 uintptr_t declaring_dex_file; 36 uint16_t declaring_field_idx; 37 bool is_volatile; 38 }; 39 40 struct MIRDef { 41 static constexpr size_t kMaxSsaDefs = 2; 42 static constexpr size_t kMaxSsaUses = 4; 43 44 Instruction::Code opcode; 45 int64_t value; 46 uint32_t field_info; 47 size_t num_uses; 48 int32_t uses[kMaxSsaUses]; 49 size_t num_defs; 50 int32_t defs[kMaxSsaDefs]; 51 }; 52 53 #define DEF_CONST(opcode, reg, value) \ 54 { opcode, value, 0u, 0, { }, 1, { reg } } 55 #define DEF_CONST_WIDE(opcode, reg, value) \ 56 { opcode, value, 0u, 0, { }, 2, { reg, reg + 1 } } 57 #define DEF_CONST_STRING(opcode, reg, index) \ 58 { opcode, index, 0u, 0, { }, 1, { reg } } 59 #define DEF_IGET(opcode, reg, obj, field_info) \ 60 { opcode, 0u, field_info, 1, { obj }, 1, { reg } } 61 #define DEF_IGET_WIDE(opcode, reg, obj, field_info) \ 62 { opcode, 0u, field_info, 1, { obj }, 2, { reg, reg + 1 } } 63 #define DEF_IPUT(opcode, reg, obj, field_info) \ 64 { opcode, 0u, field_info, 2, { reg, obj }, 0, { } } 65 #define DEF_IPUT_WIDE(opcode, reg, obj, field_info) \ 66 { opcode, 0u, field_info, 3, { reg, reg + 1, obj }, 0, { } } 67 #define DEF_SGET(opcode, reg, field_info) \ 68 { opcode, 0u, field_info, 0, { }, 1, { reg } } 69 #define DEF_SGET_WIDE(opcode, reg, field_info) \ 70 { opcode, 0u, field_info, 0, { }, 2, { reg, reg + 1 } } 71 #define DEF_SPUT(opcode, reg, field_info) \ 72 { opcode, 0u, field_info, 1, { reg }, 0, { } } 73 #define DEF_SPUT_WIDE(opcode, reg, field_info) \ 74 { opcode, 0u, field_info, 2, { reg, reg + 1 }, 0, { } } 75 #define DEF_AGET(opcode, reg, obj, idx) \ 76 { opcode, 0u, 0u, 2, { obj, idx }, 1, { reg } } 77 #define DEF_AGET_WIDE(opcode, reg, obj, idx) \ 78 { opcode, 0u, 0u, 2, { obj, idx }, 2, { reg, reg + 1 } } 79 #define DEF_APUT(opcode, reg, obj, idx) \ 80 { opcode, 0u, 0u, 3, { reg, obj, idx }, 0, { } } 81 #define DEF_APUT_WIDE(opcode, reg, obj, idx) \ 82 { opcode, 0u, 0u, 4, { reg, reg + 1, obj, idx }, 0, { } } 83 #define DEF_INVOKE1(opcode, reg) \ 84 { opcode, 0u, 0u, 1, { reg }, 0, { } } 85 #define DEF_UNIQUE_REF(opcode, reg) \ 86 { opcode, 0u, 0u, 0, { }, 1, { reg } } // CONST_CLASS, CONST_STRING, NEW_ARRAY, ... 87 88 void DoPrepareIFields(const IFieldDef* defs, size_t count) { 89 cu_.mir_graph->ifield_lowering_infos_.Reset(); 90 cu_.mir_graph->ifield_lowering_infos_.Resize(count); 91 for (size_t i = 0u; i != count; ++i) { 92 const IFieldDef* def = &defs[i]; 93 MirIFieldLoweringInfo field_info(def->field_idx); 94 if (def->declaring_dex_file != 0u) { 95 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 96 field_info.declaring_field_idx_ = def->declaring_field_idx; 97 field_info.flags_ = 0u | // Without kFlagIsStatic. 98 (def->is_volatile ? MirIFieldLoweringInfo::kFlagIsVolatile : 0u); 99 } 100 cu_.mir_graph->ifield_lowering_infos_.Insert(field_info); 101 } 102 } 103 104 template <size_t count> 105 void PrepareIFields(const IFieldDef (&defs)[count]) { 106 DoPrepareIFields(defs, count); 107 } 108 109 void DoPrepareSFields(const SFieldDef* defs, size_t count) { 110 cu_.mir_graph->sfield_lowering_infos_.Reset(); 111 cu_.mir_graph->sfield_lowering_infos_.Resize(count); 112 for (size_t i = 0u; i != count; ++i) { 113 const SFieldDef* def = &defs[i]; 114 MirSFieldLoweringInfo field_info(def->field_idx); 115 // Mark even unresolved fields as initialized. 116 field_info.flags_ = MirSFieldLoweringInfo::kFlagIsStatic | 117 MirSFieldLoweringInfo::kFlagIsInitialized; 118 if (def->declaring_dex_file != 0u) { 119 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 120 field_info.declaring_field_idx_ = def->declaring_field_idx; 121 field_info.flags_ |= (def->is_volatile ? MirSFieldLoweringInfo::kFlagIsVolatile : 0u); 122 } 123 cu_.mir_graph->sfield_lowering_infos_.Insert(field_info); 124 } 125 } 126 127 template <size_t count> 128 void PrepareSFields(const SFieldDef (&defs)[count]) { 129 DoPrepareSFields(defs, count); 130 } 131 132 void DoPrepareMIRs(const MIRDef* defs, size_t count) { 133 mir_count_ = count; 134 mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR)); 135 ssa_reps_.resize(count); 136 for (size_t i = 0u; i != count; ++i) { 137 const MIRDef* def = &defs[i]; 138 MIR* mir = &mirs_[i]; 139 mir->dalvikInsn.opcode = def->opcode; 140 mir->dalvikInsn.vB = static_cast<int32_t>(def->value); 141 mir->dalvikInsn.vB_wide = def->value; 142 if (def->opcode >= Instruction::IGET && def->opcode <= Instruction::IPUT_SHORT) { 143 ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.Size()); 144 mir->meta.ifield_lowering_info = def->field_info; 145 } else if (def->opcode >= Instruction::SGET && def->opcode <= Instruction::SPUT_SHORT) { 146 ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.Size()); 147 mir->meta.sfield_lowering_info = def->field_info; 148 } 149 mir->ssa_rep = &ssa_reps_[i]; 150 mir->ssa_rep->num_uses = def->num_uses; 151 mir->ssa_rep->uses = const_cast<int32_t*>(def->uses); // Not modified by LVN. 152 mir->ssa_rep->fp_use = nullptr; // Not used by LVN. 153 mir->ssa_rep->num_defs = def->num_defs; 154 mir->ssa_rep->defs = const_cast<int32_t*>(def->defs); // Not modified by LVN. 155 mir->ssa_rep->fp_def = nullptr; // Not used by LVN. 156 mir->dalvikInsn.opcode = def->opcode; 157 mir->offset = i; // LVN uses offset only for debug output 158 mir->optimization_flags = 0u; 159 160 if (i != 0u) { 161 mirs_[i - 1u].next = mir; 162 } 163 } 164 mirs_[count - 1u].next = nullptr; 165 } 166 167 template <size_t count> 168 void PrepareMIRs(const MIRDef (&defs)[count]) { 169 DoPrepareMIRs(defs, count); 170 } 171 172 void MakeSFieldUninitialized(uint32_t sfield_index) { 173 CHECK_LT(sfield_index, cu_.mir_graph->sfield_lowering_infos_.Size()); 174 cu_.mir_graph->sfield_lowering_infos_.GetRawStorage()[sfield_index].flags_ &= 175 ~MirSFieldLoweringInfo::kFlagIsInitialized; 176 } 177 178 void PerformLVN() { 179 value_names_.resize(mir_count_); 180 for (size_t i = 0; i != mir_count_; ++i) { 181 value_names_[i] = lvn_->GetValueNumber(&mirs_[i]); 182 } 183 EXPECT_TRUE(gvn_->Good()); 184 } 185 186 LocalValueNumberingTest() 187 : pool_(), 188 cu_(&pool_), 189 mir_count_(0u), 190 mirs_(nullptr), 191 ssa_reps_(), 192 allocator_(), 193 gvn_(), 194 lvn_(), 195 value_names_() { 196 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena)); 197 allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack)); 198 gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get())); 199 lvn_.reset(new (allocator_.get()) LocalValueNumbering(gvn_.get(), 0u, allocator_.get())); 200 gvn_->AllowModifications(); 201 } 202 203 ArenaPool pool_; 204 CompilationUnit cu_; 205 size_t mir_count_; 206 MIR* mirs_; 207 std::vector<SSARepresentation> ssa_reps_; 208 std::unique_ptr<ScopedArenaAllocator> allocator_; 209 std::unique_ptr<GlobalValueNumbering> gvn_; 210 std::unique_ptr<LocalValueNumbering> lvn_; 211 std::vector<uint16_t> value_names_; 212 }; 213 214 TEST_F(LocalValueNumberingTest, IGetIGetInvokeIGet) { 215 static const IFieldDef ifields[] = { 216 { 1u, 1u, 1u, false }, 217 }; 218 static const MIRDef mirs[] = { 219 DEF_IGET(Instruction::IGET, 0u, 10u, 0u), 220 DEF_IGET(Instruction::IGET, 1u, 10u, 0u), 221 DEF_INVOKE1(Instruction::INVOKE_VIRTUAL, 11u), 222 DEF_IGET(Instruction::IGET, 2u, 10u, 0u), 223 }; 224 225 PrepareIFields(ifields); 226 PrepareMIRs(mirs); 227 PerformLVN(); 228 ASSERT_EQ(value_names_.size(), 4u); 229 EXPECT_EQ(value_names_[0], value_names_[1]); 230 EXPECT_NE(value_names_[0], value_names_[3]); 231 EXPECT_EQ(mirs_[0].optimization_flags, 0u); 232 EXPECT_EQ(mirs_[1].optimization_flags, MIR_IGNORE_NULL_CHECK); 233 EXPECT_EQ(mirs_[2].optimization_flags, 0u); 234 EXPECT_EQ(mirs_[3].optimization_flags, MIR_IGNORE_NULL_CHECK); 235 } 236 237 TEST_F(LocalValueNumberingTest, IGetIPutIGetIGetIGet) { 238 static const IFieldDef ifields[] = { 239 { 1u, 1u, 1u, false }, 240 { 2u, 1u, 2u, false }, 241 }; 242 static const MIRDef mirs[] = { 243 DEF_IGET(Instruction::IGET_OBJECT, 0u, 10u, 0u), 244 DEF_IPUT(Instruction::IPUT_OBJECT, 1u, 11u, 0u), // May alias. 245 DEF_IGET(Instruction::IGET_OBJECT, 2u, 10u, 0u), 246 DEF_IGET(Instruction::IGET, 3u, 0u, 1u), 247 DEF_IGET(Instruction::IGET, 4u, 2u, 1u), 248 }; 249 250 PrepareIFields(ifields); 251 PrepareMIRs(mirs); 252 PerformLVN(); 253 ASSERT_EQ(value_names_.size(), 5u); 254 EXPECT_NE(value_names_[0], value_names_[2]); 255 EXPECT_NE(value_names_[3], value_names_[4]); 256 for (size_t i = 0; i != arraysize(mirs); ++i) { 257 EXPECT_EQ((i == 2u) ? MIR_IGNORE_NULL_CHECK : 0, 258 mirs_[i].optimization_flags) << i; 259 } 260 } 261 262 TEST_F(LocalValueNumberingTest, UniquePreserve1) { 263 static const IFieldDef ifields[] = { 264 { 1u, 1u, 1u, false }, 265 }; 266 static const MIRDef mirs[] = { 267 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 10u), 268 DEF_IGET(Instruction::IGET, 0u, 10u, 0u), 269 DEF_IPUT(Instruction::IPUT, 1u, 11u, 0u), // No aliasing since 10u is unique. 270 DEF_IGET(Instruction::IGET, 2u, 10u, 0u), 271 }; 272 273 PrepareIFields(ifields); 274 PrepareMIRs(mirs); 275 PerformLVN(); 276 ASSERT_EQ(value_names_.size(), 4u); 277 EXPECT_EQ(value_names_[1], value_names_[3]); 278 for (size_t i = 0; i != arraysize(mirs); ++i) { 279 EXPECT_EQ((i == 1u || i == 3u) ? MIR_IGNORE_NULL_CHECK : 0, 280 mirs_[i].optimization_flags) << i; 281 } 282 } 283 284 TEST_F(LocalValueNumberingTest, UniquePreserve2) { 285 static const IFieldDef ifields[] = { 286 { 1u, 1u, 1u, false }, 287 }; 288 static const MIRDef mirs[] = { 289 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 11u), 290 DEF_IGET(Instruction::IGET, 0u, 10u, 0u), 291 DEF_IPUT(Instruction::IPUT, 1u, 11u, 0u), // No aliasing since 11u is unique. 292 DEF_IGET(Instruction::IGET, 2u, 10u, 0u), 293 }; 294 295 PrepareIFields(ifields); 296 PrepareMIRs(mirs); 297 PerformLVN(); 298 ASSERT_EQ(value_names_.size(), 4u); 299 EXPECT_EQ(value_names_[1], value_names_[3]); 300 for (size_t i = 0; i != arraysize(mirs); ++i) { 301 EXPECT_EQ((i == 2u || i == 3u) ? MIR_IGNORE_NULL_CHECK : 0, 302 mirs_[i].optimization_flags) << i; 303 } 304 } 305 306 TEST_F(LocalValueNumberingTest, UniquePreserveAndEscape) { 307 static const IFieldDef ifields[] = { 308 { 1u, 1u, 1u, false }, 309 }; 310 static const MIRDef mirs[] = { 311 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 10u), 312 DEF_IGET(Instruction::IGET, 0u, 10u, 0u), 313 DEF_INVOKE1(Instruction::INVOKE_VIRTUAL, 11u), // 10u still unique. 314 DEF_IGET(Instruction::IGET, 2u, 10u, 0u), 315 DEF_INVOKE1(Instruction::INVOKE_VIRTUAL, 10u), // 10u not unique anymore. 316 DEF_IGET(Instruction::IGET, 3u, 10u, 0u), 317 }; 318 319 PrepareIFields(ifields); 320 PrepareMIRs(mirs); 321 PerformLVN(); 322 ASSERT_EQ(value_names_.size(), 6u); 323 EXPECT_EQ(value_names_[1], value_names_[3]); 324 EXPECT_NE(value_names_[1], value_names_[5]); 325 for (size_t i = 0; i != arraysize(mirs); ++i) { 326 EXPECT_EQ((i == 1u || i == 3u || i == 4u || i == 5u) ? MIR_IGNORE_NULL_CHECK : 0, 327 mirs_[i].optimization_flags) << i; 328 } 329 } 330 331 TEST_F(LocalValueNumberingTest, Volatile) { 332 static const IFieldDef ifields[] = { 333 { 1u, 1u, 1u, false }, 334 { 2u, 1u, 2u, true }, 335 }; 336 static const MIRDef mirs[] = { 337 DEF_IGET(Instruction::IGET, 0u, 10u, 1u), // Volatile. 338 DEF_IGET(Instruction::IGET, 1u, 0u, 0u), // Non-volatile. 339 DEF_IGET(Instruction::IGET, 2u, 10u, 1u), // Volatile. 340 DEF_IGET(Instruction::IGET, 3u, 2u, 1u), // Non-volatile. 341 }; 342 343 PrepareIFields(ifields); 344 PrepareMIRs(mirs); 345 PerformLVN(); 346 ASSERT_EQ(value_names_.size(), 4u); 347 EXPECT_NE(value_names_[0], value_names_[2]); // Volatile has always different value name. 348 EXPECT_NE(value_names_[1], value_names_[3]); // Used different base because of volatile. 349 for (size_t i = 0; i != arraysize(mirs); ++i) { 350 EXPECT_EQ((i == 2u) ? MIR_IGNORE_NULL_CHECK : 0, 351 mirs_[i].optimization_flags) << i; 352 } 353 } 354 355 TEST_F(LocalValueNumberingTest, UnresolvedIField) { 356 static const IFieldDef ifields[] = { 357 { 1u, 1u, 1u, false }, // Resolved field #1. 358 { 2u, 1u, 2u, false }, // Resolved field #2. 359 { 3u, 0u, 0u, false }, // Unresolved field. 360 }; 361 static const MIRDef mirs[] = { 362 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 20u), 363 DEF_IGET(Instruction::IGET, 1u, 20u, 0u), // Resolved field #1, unique object. 364 DEF_IGET(Instruction::IGET, 2u, 21u, 0u), // Resolved field #1. 365 DEF_IGET_WIDE(Instruction::IGET_WIDE, 3u, 21u, 1u), // Resolved field #2. 366 DEF_IGET(Instruction::IGET, 4u, 22u, 2u), // IGET doesn't clobber anything. 367 DEF_IGET(Instruction::IGET, 5u, 20u, 0u), // Resolved field #1, unique object. 368 DEF_IGET(Instruction::IGET, 6u, 21u, 0u), // Resolved field #1. 369 DEF_IGET_WIDE(Instruction::IGET_WIDE, 7u, 21u, 1u), // Resolved field #2. 370 DEF_IPUT(Instruction::IPUT, 8u, 22u, 2u), // IPUT clobbers field #1 (#2 is wide). 371 DEF_IGET(Instruction::IGET, 9u, 20u, 0u), // Resolved field #1, unique object. 372 DEF_IGET(Instruction::IGET, 10u, 21u, 0u), // Resolved field #1, new value name. 373 DEF_IGET_WIDE(Instruction::IGET_WIDE, 11u, 21u, 1u), // Resolved field #2. 374 DEF_IGET_WIDE(Instruction::IGET_WIDE, 12u, 20u, 1u), // Resolved field #2, unique object. 375 DEF_IPUT(Instruction::IPUT, 13u, 20u, 2u), // IPUT clobbers field #1 (#2 is wide). 376 DEF_IGET(Instruction::IGET, 14u, 20u, 0u), // Resolved field #1, unique object. 377 DEF_IGET_WIDE(Instruction::IGET_WIDE, 15u, 20u, 1u), // Resolved field #2, unique object. 378 }; 379 380 PrepareIFields(ifields); 381 PrepareMIRs(mirs); 382 PerformLVN(); 383 ASSERT_EQ(value_names_.size(), 16u); 384 EXPECT_EQ(value_names_[1], value_names_[5]); 385 EXPECT_EQ(value_names_[2], value_names_[6]); 386 EXPECT_EQ(value_names_[3], value_names_[7]); 387 EXPECT_EQ(value_names_[1], value_names_[9]); 388 EXPECT_NE(value_names_[2], value_names_[10]); // This aliased with unresolved IPUT. 389 EXPECT_EQ(value_names_[3], value_names_[11]); 390 EXPECT_EQ(value_names_[12], value_names_[15]); 391 EXPECT_NE(value_names_[1], value_names_[14]); // This aliased with unresolved IPUT. 392 EXPECT_EQ(mirs_[0].optimization_flags, 0u); 393 EXPECT_EQ(mirs_[1].optimization_flags, MIR_IGNORE_NULL_CHECK); 394 EXPECT_EQ(mirs_[2].optimization_flags, 0u); 395 EXPECT_EQ(mirs_[3].optimization_flags, MIR_IGNORE_NULL_CHECK); 396 EXPECT_EQ(mirs_[4].optimization_flags, 0u); 397 for (size_t i = 5u; i != mir_count_; ++i) { 398 EXPECT_EQ((i == 1u || i == 3u || i >=5u) ? MIR_IGNORE_NULL_CHECK : 0, 399 mirs_[i].optimization_flags) << i; 400 } 401 } 402 403 TEST_F(LocalValueNumberingTest, UnresolvedSField) { 404 static const SFieldDef sfields[] = { 405 { 1u, 1u, 1u, false }, // Resolved field #1. 406 { 2u, 1u, 2u, false }, // Resolved field #2. 407 { 3u, 0u, 0u, false }, // Unresolved field. 408 }; 409 static const MIRDef mirs[] = { 410 DEF_SGET(Instruction::SGET, 0u, 0u), // Resolved field #1. 411 DEF_SGET_WIDE(Instruction::SGET_WIDE, 1u, 1u), // Resolved field #2. 412 DEF_SGET(Instruction::SGET, 2u, 2u), // SGET doesn't clobber anything. 413 DEF_SGET(Instruction::SGET, 3u, 0u), // Resolved field #1. 414 DEF_SGET_WIDE(Instruction::SGET_WIDE, 4u, 1u), // Resolved field #2. 415 DEF_SPUT(Instruction::SPUT, 5u, 2u), // SPUT clobbers field #1 (#2 is wide). 416 DEF_SGET(Instruction::SGET, 6u, 0u), // Resolved field #1. 417 DEF_SGET_WIDE(Instruction::SGET_WIDE, 7u, 1u), // Resolved field #2. 418 }; 419 420 PrepareSFields(sfields); 421 PrepareMIRs(mirs); 422 PerformLVN(); 423 ASSERT_EQ(value_names_.size(), 8u); 424 EXPECT_EQ(value_names_[0], value_names_[3]); 425 EXPECT_EQ(value_names_[1], value_names_[4]); 426 EXPECT_NE(value_names_[0], value_names_[6]); // This aliased with unresolved IPUT. 427 EXPECT_EQ(value_names_[1], value_names_[7]); 428 for (size_t i = 0u; i != mir_count_; ++i) { 429 EXPECT_EQ(0, mirs_[i].optimization_flags) << i; 430 } 431 } 432 433 TEST_F(LocalValueNumberingTest, UninitializedSField) { 434 static const IFieldDef ifields[] = { 435 { 1u, 1u, 1u, false }, // Resolved field #1. 436 }; 437 static const SFieldDef sfields[] = { 438 { 1u, 1u, 1u, false }, // Resolved field #1. 439 { 2u, 1u, 2u, false }, // Resolved field #2; uninitialized. 440 }; 441 static const MIRDef mirs[] = { 442 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 200u), 443 DEF_IGET(Instruction::IGET, 1u, 100u, 0u), 444 DEF_IGET(Instruction::IGET, 2u, 200u, 0u), 445 DEF_SGET(Instruction::SGET, 3u, 0u), 446 DEF_SGET(Instruction::SGET, 4u, 1u), // Can call <clinit>(). 447 DEF_IGET(Instruction::IGET, 5u, 100u, 0u), // Differs from 1u. 448 DEF_IGET(Instruction::IGET, 6u, 200u, 0u), // Same as 2u. 449 DEF_SGET(Instruction::SGET, 7u, 0u), // Differs from 3u. 450 }; 451 452 PrepareIFields(ifields); 453 PrepareSFields(sfields); 454 MakeSFieldUninitialized(1u); 455 PrepareMIRs(mirs); 456 PerformLVN(); 457 ASSERT_EQ(value_names_.size(), 8u); 458 EXPECT_NE(value_names_[1], value_names_[5]); 459 EXPECT_EQ(value_names_[2], value_names_[6]); 460 EXPECT_NE(value_names_[3], value_names_[7]); 461 } 462 463 TEST_F(LocalValueNumberingTest, ConstString) { 464 static const MIRDef mirs[] = { 465 DEF_CONST_STRING(Instruction::CONST_STRING, 0u, 0u), 466 DEF_CONST_STRING(Instruction::CONST_STRING, 1u, 0u), 467 DEF_CONST_STRING(Instruction::CONST_STRING, 2u, 2u), 468 DEF_CONST_STRING(Instruction::CONST_STRING, 3u, 0u), 469 DEF_INVOKE1(Instruction::INVOKE_DIRECT, 2u), 470 DEF_CONST_STRING(Instruction::CONST_STRING, 4u, 2u), 471 }; 472 473 PrepareMIRs(mirs); 474 PerformLVN(); 475 ASSERT_EQ(value_names_.size(), 6u); 476 EXPECT_EQ(value_names_[1], value_names_[0]); 477 EXPECT_NE(value_names_[2], value_names_[0]); 478 EXPECT_EQ(value_names_[3], value_names_[0]); 479 EXPECT_EQ(value_names_[5], value_names_[2]); 480 } 481 482 TEST_F(LocalValueNumberingTest, SameValueInDifferentMemoryLocations) { 483 static const IFieldDef ifields[] = { 484 { 1u, 1u, 1u, false }, 485 { 2u, 1u, 2u, false }, 486 }; 487 static const SFieldDef sfields[] = { 488 { 3u, 1u, 3u, false }, 489 }; 490 static const MIRDef mirs[] = { 491 DEF_UNIQUE_REF(Instruction::NEW_ARRAY, 201u), 492 DEF_IGET(Instruction::IGET, 0u, 100u, 0u), 493 DEF_IPUT(Instruction::IPUT, 0u, 100u, 1u), 494 DEF_IPUT(Instruction::IPUT, 0u, 101u, 1u), 495 DEF_APUT(Instruction::APUT, 0u, 200u, 300u), 496 DEF_APUT(Instruction::APUT, 0u, 200u, 301u), 497 DEF_APUT(Instruction::APUT, 0u, 201u, 300u), 498 DEF_APUT(Instruction::APUT, 0u, 201u, 301u), 499 DEF_SPUT(Instruction::SPUT, 0u, 0u), 500 DEF_IGET(Instruction::IGET, 9u, 100u, 0u), 501 DEF_IGET(Instruction::IGET, 10u, 100u, 1u), 502 DEF_IGET(Instruction::IGET, 11u, 101u, 1u), 503 DEF_AGET(Instruction::AGET, 12u, 200u, 300u), 504 DEF_AGET(Instruction::AGET, 13u, 200u, 301u), 505 DEF_AGET(Instruction::AGET, 14u, 201u, 300u), 506 DEF_AGET(Instruction::AGET, 15u, 201u, 301u), 507 DEF_SGET(Instruction::SGET, 16u, 0u), 508 }; 509 510 PrepareIFields(ifields); 511 PrepareSFields(sfields); 512 PrepareMIRs(mirs); 513 PerformLVN(); 514 ASSERT_EQ(value_names_.size(), 17u); 515 for (size_t i = 9; i != arraysize(mirs); ++i) { 516 EXPECT_EQ(value_names_[1], value_names_[i]) << i; 517 } 518 for (size_t i = 0; i != arraysize(mirs); ++i) { 519 int expected_flags = 520 ((i == 2u || (i >= 5u && i <= 7u) || (i >= 9u && i <= 15u)) ? MIR_IGNORE_NULL_CHECK : 0) | 521 ((i >= 12u && i <= 15u) ? MIR_IGNORE_RANGE_CHECK : 0); 522 EXPECT_EQ(expected_flags, mirs_[i].optimization_flags) << i; 523 } 524 } 525 526 TEST_F(LocalValueNumberingTest, UniqueArrayAliasing) { 527 static const MIRDef mirs[] = { 528 DEF_UNIQUE_REF(Instruction::NEW_ARRAY, 20u), 529 DEF_AGET(Instruction::AGET, 1u, 20u, 40u), 530 DEF_APUT(Instruction::APUT, 2u, 20u, 41u), // May alias with index for sreg 40u. 531 DEF_AGET(Instruction::AGET, 3u, 20u, 40u), 532 }; 533 534 PrepareMIRs(mirs); 535 PerformLVN(); 536 ASSERT_EQ(value_names_.size(), 4u); 537 EXPECT_NE(value_names_[1], value_names_[3]); 538 for (size_t i = 0; i != arraysize(mirs); ++i) { 539 int expected_flags = 540 ((i >= 1u) ? MIR_IGNORE_NULL_CHECK : 0) | 541 ((i == 3u) ? MIR_IGNORE_RANGE_CHECK : 0); 542 EXPECT_EQ(expected_flags, mirs_[i].optimization_flags) << i; 543 } 544 } 545 546 TEST_F(LocalValueNumberingTest, EscapingRefs) { 547 static const IFieldDef ifields[] = { 548 { 1u, 1u, 1u, false }, // Field #1. 549 { 2u, 1u, 2u, false }, // Field #2. 550 { 3u, 1u, 3u, false }, // Reference field for storing escaping refs. 551 { 4u, 1u, 4u, false }, // Wide. 552 { 5u, 0u, 0u, false }, // Unresolved field, int. 553 { 6u, 0u, 0u, false }, // Unresolved field, wide. 554 }; 555 static const MIRDef mirs[] = { 556 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 20u), 557 DEF_IGET(Instruction::IGET, 1u, 20u, 0u), 558 DEF_IGET(Instruction::IGET, 2u, 20u, 1u), 559 DEF_IPUT(Instruction::IPUT_OBJECT, 20u, 30u, 2u), // Ref escapes. 560 DEF_IGET(Instruction::IGET, 4u, 20u, 0u), 561 DEF_IGET(Instruction::IGET, 5u, 20u, 1u), 562 DEF_IPUT(Instruction::IPUT, 6u, 31u, 0u), // May alias with field #1. 563 DEF_IGET(Instruction::IGET, 7u, 20u, 0u), // New value. 564 DEF_IGET(Instruction::IGET, 8u, 20u, 1u), // Still the same. 565 DEF_IPUT_WIDE(Instruction::IPUT_WIDE, 9u, 31u, 3u), // No aliasing, different type. 566 DEF_IGET(Instruction::IGET, 10u, 20u, 0u), 567 DEF_IGET(Instruction::IGET, 11u, 20u, 1u), 568 DEF_IPUT_WIDE(Instruction::IPUT_WIDE, 12u, 31u, 5u), // No aliasing, different type. 569 DEF_IGET(Instruction::IGET, 13u, 20u, 0u), 570 DEF_IGET(Instruction::IGET, 14u, 20u, 1u), 571 DEF_IPUT(Instruction::IPUT, 15u, 31u, 4u), // Aliasing, same type. 572 DEF_IGET(Instruction::IGET, 16u, 20u, 0u), 573 DEF_IGET(Instruction::IGET, 17u, 20u, 1u), 574 }; 575 576 PrepareIFields(ifields); 577 PrepareMIRs(mirs); 578 PerformLVN(); 579 ASSERT_EQ(value_names_.size(), 18u); 580 EXPECT_EQ(value_names_[1], value_names_[4]); 581 EXPECT_EQ(value_names_[2], value_names_[5]); 582 EXPECT_NE(value_names_[4], value_names_[7]); // New value. 583 EXPECT_EQ(value_names_[5], value_names_[8]); 584 EXPECT_EQ(value_names_[7], value_names_[10]); 585 EXPECT_EQ(value_names_[8], value_names_[11]); 586 EXPECT_EQ(value_names_[10], value_names_[13]); 587 EXPECT_EQ(value_names_[11], value_names_[14]); 588 EXPECT_NE(value_names_[13], value_names_[16]); // New value. 589 EXPECT_NE(value_names_[14], value_names_[17]); // New value. 590 for (size_t i = 0u; i != mir_count_; ++i) { 591 int expected = (i != 0u && i != 3u && i != 6u) ? MIR_IGNORE_NULL_CHECK : 0; 592 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 593 } 594 } 595 596 TEST_F(LocalValueNumberingTest, EscapingArrayRefs) { 597 static const MIRDef mirs[] = { 598 DEF_UNIQUE_REF(Instruction::NEW_ARRAY, 20u), 599 DEF_AGET(Instruction::AGET, 1u, 20u, 40u), 600 DEF_AGET(Instruction::AGET, 2u, 20u, 41u), 601 DEF_APUT(Instruction::APUT_OBJECT, 20u, 30u, 42u), // Array ref escapes. 602 DEF_AGET(Instruction::AGET, 4u, 20u, 40u), 603 DEF_AGET(Instruction::AGET, 5u, 20u, 41u), 604 DEF_APUT_WIDE(Instruction::APUT_WIDE, 6u, 31u, 43u), // No aliasing, different type. 605 DEF_AGET(Instruction::AGET, 7u, 20u, 40u), 606 DEF_AGET(Instruction::AGET, 8u, 20u, 41u), 607 DEF_APUT(Instruction::APUT, 9u, 32u, 40u), // May alias with all elements. 608 DEF_AGET(Instruction::AGET, 10u, 20u, 40u), // New value (same index name). 609 DEF_AGET(Instruction::AGET, 11u, 20u, 41u), // New value (different index name). 610 }; 611 612 PrepareMIRs(mirs); 613 PerformLVN(); 614 ASSERT_EQ(value_names_.size(), 12u); 615 EXPECT_EQ(value_names_[1], value_names_[4]); 616 EXPECT_EQ(value_names_[2], value_names_[5]); 617 EXPECT_EQ(value_names_[4], value_names_[7]); 618 EXPECT_EQ(value_names_[5], value_names_[8]); 619 EXPECT_NE(value_names_[7], value_names_[10]); // New value. 620 EXPECT_NE(value_names_[8], value_names_[11]); // New value. 621 for (size_t i = 0u; i != mir_count_; ++i) { 622 int expected = 623 ((i != 0u && i != 3u && i != 6u && i != 9u) ? MIR_IGNORE_NULL_CHECK : 0u) | 624 ((i >= 4 && i != 6u && i != 9u) ? MIR_IGNORE_RANGE_CHECK : 0u); 625 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 626 } 627 } 628 629 TEST_F(LocalValueNumberingTest, StoringSameValueKeepsMemoryVersion) { 630 static const IFieldDef ifields[] = { 631 { 1u, 1u, 1u, false }, 632 { 2u, 1u, 2u, false }, 633 }; 634 static const SFieldDef sfields[] = { 635 { 2u, 1u, 2u, false }, 636 }; 637 static const MIRDef mirs[] = { 638 DEF_IGET(Instruction::IGET, 0u, 30u, 0u), 639 DEF_IGET(Instruction::IGET, 1u, 31u, 0u), 640 DEF_IPUT(Instruction::IPUT, 1u, 31u, 0u), // Store the same value. 641 DEF_IGET(Instruction::IGET, 3u, 30u, 0u), 642 DEF_AGET(Instruction::AGET, 4u, 32u, 40u), 643 DEF_AGET(Instruction::AGET, 5u, 33u, 40u), 644 DEF_APUT(Instruction::APUT, 5u, 33u, 40u), // Store the same value. 645 DEF_AGET(Instruction::AGET, 7u, 32u, 40u), 646 DEF_SGET(Instruction::SGET, 8u, 0u), 647 DEF_SPUT(Instruction::SPUT, 8u, 0u), // Store the same value. 648 DEF_SGET(Instruction::SGET, 10u, 0u), 649 DEF_UNIQUE_REF(Instruction::NEW_INSTANCE, 50u), // Test with unique references. 650 { Instruction::FILLED_NEW_ARRAY, 0, 0u, 2, { 12u, 13u }, 0, { } }, 651 DEF_UNIQUE_REF(Instruction::MOVE_RESULT_OBJECT, 51u), 652 DEF_IGET(Instruction::IGET, 14u, 50u, 0u), 653 DEF_IGET(Instruction::IGET, 15u, 50u, 1u), 654 DEF_IPUT(Instruction::IPUT, 15u, 50u, 1u), // Store the same value. 655 DEF_IGET(Instruction::IGET, 17u, 50u, 0u), 656 DEF_AGET(Instruction::AGET, 18u, 51u, 40u), 657 DEF_AGET(Instruction::AGET, 19u, 51u, 41u), 658 DEF_APUT(Instruction::APUT, 19u, 51u, 41u), // Store the same value. 659 DEF_AGET(Instruction::AGET, 21u, 51u, 40u), 660 }; 661 662 PrepareIFields(ifields); 663 PrepareSFields(sfields); 664 PrepareMIRs(mirs); 665 PerformLVN(); 666 ASSERT_EQ(value_names_.size(), 22u); 667 EXPECT_NE(value_names_[0], value_names_[1]); 668 EXPECT_EQ(value_names_[0], value_names_[3]); 669 EXPECT_NE(value_names_[4], value_names_[5]); 670 EXPECT_EQ(value_names_[4], value_names_[7]); 671 EXPECT_EQ(value_names_[8], value_names_[10]); 672 EXPECT_NE(value_names_[14], value_names_[15]); 673 EXPECT_EQ(value_names_[14], value_names_[17]); 674 EXPECT_NE(value_names_[18], value_names_[19]); 675 EXPECT_EQ(value_names_[18], value_names_[21]); 676 for (size_t i = 0u; i != mir_count_; ++i) { 677 int expected = 678 ((i == 2u || i == 3u || i == 6u || i == 7u || (i >= 14u)) ? MIR_IGNORE_NULL_CHECK : 0u) | 679 ((i == 6u || i == 7u || i >= 20u) ? MIR_IGNORE_RANGE_CHECK : 0u); 680 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 681 } 682 } 683 684 TEST_F(LocalValueNumberingTest, FilledNewArrayTracking) { 685 if (!kLocalValueNumberingEnableFilledNewArrayTracking) { 686 // Feature disabled. 687 return; 688 } 689 static const MIRDef mirs[] = { 690 DEF_CONST(Instruction::CONST, 0u, 100), 691 DEF_CONST(Instruction::CONST, 1u, 200), 692 { Instruction::FILLED_NEW_ARRAY, 0, 0u, 2, { 0u, 1u }, 0, { } }, 693 DEF_UNIQUE_REF(Instruction::MOVE_RESULT_OBJECT, 10u), 694 DEF_CONST(Instruction::CONST, 20u, 0), 695 DEF_CONST(Instruction::CONST, 21u, 1), 696 DEF_AGET(Instruction::AGET, 6u, 10u, 20u), 697 DEF_AGET(Instruction::AGET, 7u, 10u, 21u), 698 }; 699 700 PrepareMIRs(mirs); 701 PerformLVN(); 702 ASSERT_EQ(value_names_.size(), 8u); 703 EXPECT_EQ(value_names_[0], value_names_[6]); 704 EXPECT_EQ(value_names_[1], value_names_[7]); 705 for (size_t i = 0u; i != mir_count_; ++i) { 706 int expected = (i == 6u || i == 7u) ? (MIR_IGNORE_NULL_CHECK | MIR_IGNORE_RANGE_CHECK) : 0u; 707 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i; 708 } 709 } 710 711 TEST_F(LocalValueNumberingTest, ClInitOnSget) { 712 static const SFieldDef sfields[] = { 713 { 0u, 1u, 0u, false }, 714 { 1u, 2u, 1u, false }, 715 }; 716 static const MIRDef mirs[] = { 717 DEF_SGET(Instruction::SGET_OBJECT, 0u, 0u), 718 DEF_AGET(Instruction::AGET, 1u, 0u, 100u), 719 DEF_SGET(Instruction::SGET_OBJECT, 2u, 1u), 720 DEF_SGET(Instruction::SGET_OBJECT, 3u, 0u), 721 DEF_AGET(Instruction::AGET, 4u, 3u, 100u), 722 }; 723 724 PrepareSFields(sfields); 725 MakeSFieldUninitialized(1u); 726 PrepareMIRs(mirs); 727 PerformLVN(); 728 ASSERT_EQ(value_names_.size(), 5u); 729 EXPECT_NE(value_names_[0], value_names_[3]); 730 } 731 732 } // namespace art 733
