1 /* 2 * Copyright (C) 2015 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 "dataflow_iterator-inl.h" 18 #include "dex/mir_field_info.h" 19 #include "global_value_numbering.h" 20 #include "gvn_dead_code_elimination.h" 21 #include "local_value_numbering.h" 22 #include "gtest/gtest.h" 23 24 namespace art { 25 26 class GvnDeadCodeEliminationTest : public testing::Test { 27 protected: 28 static constexpr uint16_t kNoValue = GlobalValueNumbering::kNoValue; 29 30 struct IFieldDef { 31 uint16_t field_idx; 32 uintptr_t declaring_dex_file; 33 uint16_t declaring_field_idx; 34 bool is_volatile; 35 DexMemAccessType type; 36 }; 37 38 struct SFieldDef { 39 uint16_t field_idx; 40 uintptr_t declaring_dex_file; 41 uint16_t declaring_field_idx; 42 bool is_volatile; 43 DexMemAccessType type; 44 }; 45 46 struct BBDef { 47 static constexpr size_t kMaxSuccessors = 4; 48 static constexpr size_t kMaxPredecessors = 4; 49 50 BBType type; 51 size_t num_successors; 52 BasicBlockId successors[kMaxPredecessors]; 53 size_t num_predecessors; 54 BasicBlockId predecessors[kMaxPredecessors]; 55 }; 56 57 struct MIRDef { 58 static constexpr size_t kMaxSsaDefs = 2; 59 static constexpr size_t kMaxSsaUses = 4; 60 61 BasicBlockId bbid; 62 Instruction::Code opcode; 63 int64_t value; 64 uint32_t field_info; 65 size_t num_uses; 66 int32_t uses[kMaxSsaUses]; 67 size_t num_defs; 68 int32_t defs[kMaxSsaDefs]; 69 }; 70 71 #define DEF_SUCC0() \ 72 0u, { } 73 #define DEF_SUCC1(s1) \ 74 1u, { s1 } 75 #define DEF_SUCC2(s1, s2) \ 76 2u, { s1, s2 } 77 #define DEF_SUCC3(s1, s2, s3) \ 78 3u, { s1, s2, s3 } 79 #define DEF_SUCC4(s1, s2, s3, s4) \ 80 4u, { s1, s2, s3, s4 } 81 #define DEF_PRED0() \ 82 0u, { } 83 #define DEF_PRED1(p1) \ 84 1u, { p1 } 85 #define DEF_PRED2(p1, p2) \ 86 2u, { p1, p2 } 87 #define DEF_PRED3(p1, p2, p3) \ 88 3u, { p1, p2, p3 } 89 #define DEF_PRED4(p1, p2, p3, p4) \ 90 4u, { p1, p2, p3, p4 } 91 #define DEF_BB(type, succ, pred) \ 92 { type, succ, pred } 93 94 #define DEF_CONST(bb, opcode, reg, value) \ 95 { bb, opcode, value, 0u, 0, { }, 1, { reg } } 96 #define DEF_CONST_WIDE(bb, opcode, reg, value) \ 97 { bb, opcode, value, 0u, 0, { }, 2, { reg, reg + 1 } } 98 #define DEF_CONST_STRING(bb, opcode, reg, index) \ 99 { bb, opcode, index, 0u, 0, { }, 1, { reg } } 100 #define DEF_IGET(bb, opcode, reg, obj, field_info) \ 101 { bb, opcode, 0u, field_info, 1, { obj }, 1, { reg } } 102 #define DEF_IGET_WIDE(bb, opcode, reg, obj, field_info) \ 103 { bb, opcode, 0u, field_info, 1, { obj }, 2, { reg, reg + 1 } } 104 #define DEF_IPUT(bb, opcode, reg, obj, field_info) \ 105 { bb, opcode, 0u, field_info, 2, { reg, obj }, 0, { } } 106 #define DEF_IPUT_WIDE(bb, opcode, reg, obj, field_info) \ 107 { bb, opcode, 0u, field_info, 3, { reg, reg + 1, obj }, 0, { } } 108 #define DEF_SGET(bb, opcode, reg, field_info) \ 109 { bb, opcode, 0u, field_info, 0, { }, 1, { reg } } 110 #define DEF_SGET_WIDE(bb, opcode, reg, field_info) \ 111 { bb, opcode, 0u, field_info, 0, { }, 2, { reg, reg + 1 } } 112 #define DEF_SPUT(bb, opcode, reg, field_info) \ 113 { bb, opcode, 0u, field_info, 1, { reg }, 0, { } } 114 #define DEF_SPUT_WIDE(bb, opcode, reg, field_info) \ 115 { bb, opcode, 0u, field_info, 2, { reg, reg + 1 }, 0, { } } 116 #define DEF_AGET(bb, opcode, reg, obj, idx) \ 117 { bb, opcode, 0u, 0u, 2, { obj, idx }, 1, { reg } } 118 #define DEF_AGET_WIDE(bb, opcode, reg, obj, idx) \ 119 { bb, opcode, 0u, 0u, 2, { obj, idx }, 2, { reg, reg + 1 } } 120 #define DEF_APUT(bb, opcode, reg, obj, idx) \ 121 { bb, opcode, 0u, 0u, 3, { reg, obj, idx }, 0, { } } 122 #define DEF_APUT_WIDE(bb, opcode, reg, obj, idx) \ 123 { bb, opcode, 0u, 0u, 4, { reg, reg + 1, obj, idx }, 0, { } } 124 #define DEF_INVOKE1(bb, opcode, reg) \ 125 { bb, opcode, 0u, 0u, 1, { reg }, 0, { } } 126 #define DEF_UNIQUE_REF(bb, opcode, reg) \ 127 { bb, opcode, 0u, 0u, 0, { }, 1, { reg } } // CONST_CLASS, CONST_STRING, NEW_ARRAY, ... 128 #define DEF_IFZ(bb, opcode, reg) \ 129 { bb, opcode, 0u, 0u, 1, { reg }, 0, { } } 130 #define DEF_MOVE(bb, opcode, reg, src) \ 131 { bb, opcode, 0u, 0u, 1, { src }, 1, { reg } } 132 #define DEF_MOVE_WIDE(bb, opcode, reg, src) \ 133 { bb, opcode, 0u, 0u, 2, { src, src + 1 }, 2, { reg, reg + 1 } } 134 #define DEF_PHI2(bb, reg, src1, src2) \ 135 { bb, static_cast<Instruction::Code>(kMirOpPhi), 0, 0u, 2u, { src1, src2 }, 1, { reg } } 136 #define DEF_UNOP(bb, opcode, result, src1) \ 137 { bb, opcode, 0u, 0u, 1, { src1 }, 1, { result } } 138 #define DEF_BINOP(bb, opcode, result, src1, src2) \ 139 { bb, opcode, 0u, 0u, 2, { src1, src2 }, 1, { result } } 140 #define DEF_BINOP_WIDE(bb, opcode, result, src1, src2) \ 141 { bb, opcode, 0u, 0u, 4, { src1, src1 + 1, src2, src2 + 1 }, 2, { result, result + 1 } } 142 143 void DoPrepareIFields(const IFieldDef* defs, size_t count) { 144 cu_.mir_graph->ifield_lowering_infos_.clear(); 145 cu_.mir_graph->ifield_lowering_infos_.reserve(count); 146 for (size_t i = 0u; i != count; ++i) { 147 const IFieldDef* def = &defs[i]; 148 MirIFieldLoweringInfo field_info(def->field_idx, def->type, false); 149 if (def->declaring_dex_file != 0u) { 150 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 151 field_info.declaring_field_idx_ = def->declaring_field_idx; 152 field_info.flags_ = 153 MirIFieldLoweringInfo::kFlagFastGet | MirIFieldLoweringInfo::kFlagFastPut | 154 (field_info.flags_ & ~(def->is_volatile ? 0u : MirIFieldLoweringInfo::kFlagIsVolatile)); 155 } 156 cu_.mir_graph->ifield_lowering_infos_.push_back(field_info); 157 } 158 } 159 160 template <size_t count> 161 void PrepareIFields(const IFieldDef (&defs)[count]) { 162 DoPrepareIFields(defs, count); 163 } 164 165 void DoPrepareSFields(const SFieldDef* defs, size_t count) { 166 cu_.mir_graph->sfield_lowering_infos_.clear(); 167 cu_.mir_graph->sfield_lowering_infos_.reserve(count); 168 for (size_t i = 0u; i != count; ++i) { 169 const SFieldDef* def = &defs[i]; 170 MirSFieldLoweringInfo field_info(def->field_idx, def->type); 171 // Mark even unresolved fields as initialized. 172 field_info.flags_ |= MirSFieldLoweringInfo::kFlagClassIsInitialized; 173 // NOTE: MirSFieldLoweringInfo::kFlagClassIsInDexCache isn't used by GVN. 174 if (def->declaring_dex_file != 0u) { 175 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file); 176 field_info.declaring_field_idx_ = def->declaring_field_idx; 177 field_info.flags_ = 178 MirSFieldLoweringInfo::kFlagFastGet | MirSFieldLoweringInfo::kFlagFastPut | 179 (field_info.flags_ & ~(def->is_volatile ? 0u : MirSFieldLoweringInfo::kFlagIsVolatile)); 180 } 181 cu_.mir_graph->sfield_lowering_infos_.push_back(field_info); 182 } 183 } 184 185 template <size_t count> 186 void PrepareSFields(const SFieldDef (&defs)[count]) { 187 DoPrepareSFields(defs, count); 188 } 189 190 void DoPrepareBasicBlocks(const BBDef* defs, size_t count) { 191 cu_.mir_graph->block_id_map_.clear(); 192 cu_.mir_graph->block_list_.clear(); 193 ASSERT_LT(3u, count); // null, entry, exit and at least one bytecode block. 194 ASSERT_EQ(kNullBlock, defs[0].type); 195 ASSERT_EQ(kEntryBlock, defs[1].type); 196 ASSERT_EQ(kExitBlock, defs[2].type); 197 for (size_t i = 0u; i != count; ++i) { 198 const BBDef* def = &defs[i]; 199 BasicBlock* bb = cu_.mir_graph->CreateNewBB(def->type); 200 if (def->num_successors <= 2) { 201 bb->successor_block_list_type = kNotUsed; 202 bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u; 203 bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u; 204 } else { 205 bb->successor_block_list_type = kPackedSwitch; 206 bb->fall_through = 0u; 207 bb->taken = 0u; 208 bb->successor_blocks.reserve(def->num_successors); 209 for (size_t j = 0u; j != def->num_successors; ++j) { 210 SuccessorBlockInfo* successor_block_info = 211 static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo), 212 kArenaAllocSuccessor)); 213 successor_block_info->block = j; 214 successor_block_info->key = 0u; // Not used by class init check elimination. 215 bb->successor_blocks.push_back(successor_block_info); 216 } 217 } 218 bb->predecessors.assign(def->predecessors, def->predecessors + def->num_predecessors); 219 if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) { 220 bb->data_flow_info = static_cast<BasicBlockDataFlow*>( 221 cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo)); 222 bb->data_flow_info->live_in_v = live_in_v_; 223 bb->data_flow_info->vreg_to_ssa_map_exit = nullptr; 224 } 225 } 226 ASSERT_EQ(count, cu_.mir_graph->block_list_.size()); 227 cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_[1]; 228 ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type); 229 cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_[2]; 230 ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type); 231 } 232 233 template <size_t count> 234 void PrepareBasicBlocks(const BBDef (&defs)[count]) { 235 DoPrepareBasicBlocks(defs, count); 236 } 237 238 int SRegToVReg(int32_t s_reg, bool wide) { 239 int v_reg = cu_.mir_graph->SRegToVReg(s_reg); 240 CHECK_LT(static_cast<size_t>(v_reg), num_vregs_); 241 if (wide) { 242 CHECK_LT(static_cast<size_t>(v_reg + 1), num_vregs_); 243 } 244 return v_reg; 245 } 246 247 int SRegToVReg(int32_t* uses, size_t* use, bool wide) { 248 int v_reg = SRegToVReg(uses[*use], wide); 249 if (wide) { 250 CHECK_EQ(uses[*use] + 1, uses[*use + 1]); 251 *use += 2u; 252 } else { 253 *use += 1u; 254 } 255 return v_reg; 256 } 257 258 void DoPrepareMIRs(const MIRDef* defs, size_t count) { 259 mir_count_ = count; 260 mirs_ = reinterpret_cast<MIR*>(cu_.arena.Alloc(sizeof(MIR) * count, kArenaAllocMIR)); 261 ssa_reps_.resize(count); 262 for (size_t i = 0u; i != count; ++i) { 263 const MIRDef* def = &defs[i]; 264 MIR* mir = &mirs_[i]; 265 ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.size()); 266 BasicBlock* bb = cu_.mir_graph->block_list_[def->bbid]; 267 bb->AppendMIR(mir); 268 mir->dalvikInsn.opcode = def->opcode; 269 mir->dalvikInsn.vB = static_cast<int32_t>(def->value); 270 mir->dalvikInsn.vB_wide = def->value; 271 if (IsInstructionIGetOrIPut(def->opcode)) { 272 ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.size()); 273 mir->meta.ifield_lowering_info = def->field_info; 274 ASSERT_EQ(cu_.mir_graph->ifield_lowering_infos_[def->field_info].MemAccessType(), 275 IGetOrIPutMemAccessType(def->opcode)); 276 } else if (IsInstructionSGetOrSPut(def->opcode)) { 277 ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.size()); 278 mir->meta.sfield_lowering_info = def->field_info; 279 ASSERT_EQ(cu_.mir_graph->sfield_lowering_infos_[def->field_info].MemAccessType(), 280 SGetOrSPutMemAccessType(def->opcode)); 281 } else if (def->opcode == static_cast<Instruction::Code>(kMirOpPhi)) { 282 mir->meta.phi_incoming = 283 allocator_->AllocArray<BasicBlockId>(def->num_uses, kArenaAllocDFInfo); 284 ASSERT_EQ(def->num_uses, bb->predecessors.size()); 285 std::copy(bb->predecessors.begin(), bb->predecessors.end(), mir->meta.phi_incoming); 286 } 287 mir->ssa_rep = &ssa_reps_[i]; 288 cu_.mir_graph->AllocateSSAUseData(mir, def->num_uses); 289 std::copy_n(def->uses, def->num_uses, mir->ssa_rep->uses); 290 // Keep mir->ssa_rep->fp_use[.] zero-initialized (false). Not used by DCE, only copied. 291 cu_.mir_graph->AllocateSSADefData(mir, def->num_defs); 292 std::copy_n(def->defs, def->num_defs, mir->ssa_rep->defs); 293 // Keep mir->ssa_rep->fp_def[.] zero-initialized (false). Not used by DCE, only copied. 294 mir->dalvikInsn.opcode = def->opcode; 295 mir->offset = i; // LVN uses offset only for debug output 296 mir->optimization_flags = 0u; 297 uint64_t df_attrs = MIRGraph::GetDataFlowAttributes(mir); 298 if ((df_attrs & DF_DA) != 0) { 299 CHECK_NE(def->num_defs, 0u); 300 mir->dalvikInsn.vA = SRegToVReg(def->defs[0], (df_attrs & DF_A_WIDE) != 0); 301 bb->data_flow_info->vreg_to_ssa_map_exit[mir->dalvikInsn.vA] = def->defs[0]; 302 if ((df_attrs & DF_A_WIDE) != 0) { 303 CHECK_EQ(def->defs[0] + 1, def->defs[1]); 304 bb->data_flow_info->vreg_to_ssa_map_exit[mir->dalvikInsn.vA + 1u] = def->defs[0] + 1; 305 } 306 } 307 if ((df_attrs & (DF_UA | DF_UB | DF_UC)) != 0) { 308 size_t use = 0; 309 if ((df_attrs & DF_UA) != 0) { 310 mir->dalvikInsn.vA = SRegToVReg(mir->ssa_rep->uses, &use, (df_attrs & DF_A_WIDE) != 0); 311 } 312 if ((df_attrs & DF_UB) != 0) { 313 mir->dalvikInsn.vB = SRegToVReg(mir->ssa_rep->uses, &use, (df_attrs & DF_B_WIDE) != 0); 314 } 315 if ((df_attrs & DF_UC) != 0) { 316 mir->dalvikInsn.vC = SRegToVReg(mir->ssa_rep->uses, &use, (df_attrs & DF_C_WIDE) != 0); 317 } 318 DCHECK_EQ(def->num_uses, use); 319 } 320 } 321 DexFile::CodeItem* code_item = static_cast<DexFile::CodeItem*>( 322 cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc)); 323 code_item->insns_size_in_code_units_ = 2u * count; 324 code_item->registers_size_ = kMaxVRegs; 325 cu_.mir_graph->current_code_item_ = code_item; 326 } 327 328 template <size_t count> 329 void PrepareMIRs(const MIRDef (&defs)[count]) { 330 DoPrepareMIRs(defs, count); 331 } 332 333 template <size_t count> 334 void PrepareSRegToVRegMap(const int (&map)[count]) { 335 cu_.mir_graph->ssa_base_vregs_.assign(map, map + count); 336 num_vregs_ = *std::max_element(map, map + count) + 1u; 337 AllNodesIterator iterator(cu_.mir_graph.get()); 338 for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { 339 if (bb->data_flow_info != nullptr) { 340 bb->data_flow_info->vreg_to_ssa_map_exit = static_cast<int32_t*>( 341 cu_.arena.Alloc(sizeof(int32_t) * num_vregs_, kArenaAllocDFInfo)); 342 std::fill_n(bb->data_flow_info->vreg_to_ssa_map_exit, num_vregs_, INVALID_SREG); 343 } 344 } 345 } 346 347 void PerformGVN() { 348 cu_.mir_graph->SSATransformationStart(); 349 cu_.mir_graph->ComputeDFSOrders(); 350 cu_.mir_graph->ComputeDominators(); 351 cu_.mir_graph->ComputeTopologicalSortOrder(); 352 cu_.mir_graph->SSATransformationEnd(); 353 cu_.mir_graph->temp_.gvn.ifield_ids = GlobalValueNumbering::PrepareGvnFieldIds( 354 allocator_.get(), cu_.mir_graph->ifield_lowering_infos_); 355 cu_.mir_graph->temp_.gvn.sfield_ids = GlobalValueNumbering::PrepareGvnFieldIds( 356 allocator_.get(), cu_.mir_graph->sfield_lowering_infos_); 357 ASSERT_TRUE(gvn_ == nullptr); 358 gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get(), 359 GlobalValueNumbering::kModeGvn)); 360 value_names_.resize(mir_count_, 0xffffu); 361 LoopRepeatingTopologicalSortIterator iterator(cu_.mir_graph.get()); 362 bool change = false; 363 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) { 364 LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb); 365 if (lvn != nullptr) { 366 for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) { 367 value_names_[mir - mirs_] = lvn->GetValueNumber(mir); 368 } 369 } 370 change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb); 371 ASSERT_TRUE(gvn_->Good()); 372 } 373 } 374 375 void PerformGVNCodeModifications() { 376 ASSERT_TRUE(gvn_ != nullptr); 377 ASSERT_TRUE(gvn_->Good()); 378 gvn_->StartPostProcessing(); 379 TopologicalSortIterator iterator(cu_.mir_graph.get()); 380 for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { 381 LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb); 382 if (lvn != nullptr) { 383 for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) { 384 uint16_t value_name = lvn->GetValueNumber(mir); 385 ASSERT_EQ(value_name, value_names_[mir - mirs_]); 386 } 387 } 388 bool change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb); 389 ASSERT_FALSE(change); 390 ASSERT_TRUE(gvn_->Good()); 391 } 392 } 393 394 void FillVregToSsaRegExitMaps() { 395 // Fill in vreg_to_ssa_map_exit for each BB. 396 PreOrderDfsIterator iterator(cu_.mir_graph.get()); 397 for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { 398 if (bb->block_type == kDalvikByteCode) { 399 CHECK(!bb->predecessors.empty()); 400 BasicBlock* pred_bb = cu_.mir_graph->GetBasicBlock(bb->predecessors[0]); 401 for (size_t v_reg = 0; v_reg != num_vregs_; ++v_reg) { 402 if (bb->data_flow_info->vreg_to_ssa_map_exit[v_reg] == INVALID_SREG) { 403 bb->data_flow_info->vreg_to_ssa_map_exit[v_reg] = 404 pred_bb->data_flow_info->vreg_to_ssa_map_exit[v_reg]; 405 } 406 } 407 } 408 } 409 } 410 411 template <size_t count> 412 void MarkAsWideSRegs(const int32_t (&sregs)[count]) { 413 for (int32_t sreg : sregs) { 414 cu_.mir_graph->reg_location_[sreg].wide = true; 415 cu_.mir_graph->reg_location_[sreg + 1].wide = true; 416 cu_.mir_graph->reg_location_[sreg + 1].high_word = true; 417 } 418 } 419 420 void PerformDCE() { 421 FillVregToSsaRegExitMaps(); 422 cu_.mir_graph->GetNumOfCodeAndTempVRs(); 423 dce_.reset(new (allocator_.get()) GvnDeadCodeElimination(gvn_.get(), allocator_.get())); 424 PreOrderDfsIterator iterator(cu_.mir_graph.get()); 425 for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) { 426 if (bb->block_type == kDalvikByteCode) { 427 dce_->Apply(bb); 428 } 429 } 430 } 431 432 void PerformGVN_DCE() { 433 PerformGVN(); 434 PerformGVNCodeModifications(); // Eliminate null/range checks. 435 PerformDCE(); 436 } 437 438 template <size_t count> 439 void ExpectValueNamesNE(const size_t (&indexes)[count]) { 440 for (size_t i1 = 0; i1 != count; ++i1) { 441 size_t idx1 = indexes[i1]; 442 for (size_t i2 = i1 + 1; i2 != count; ++i2) { 443 size_t idx2 = indexes[i2]; 444 EXPECT_NE(value_names_[idx1], value_names_[idx2]) << idx1 << " " << idx2; 445 } 446 } 447 } 448 449 template <size_t count> 450 void ExpectNoNullCheck(const size_t (&indexes)[count]) { 451 for (size_t i = 0; i != count; ++i) { 452 size_t idx = indexes[i]; 453 EXPECT_EQ(MIR_IGNORE_NULL_CHECK, mirs_[idx].optimization_flags & MIR_IGNORE_NULL_CHECK) 454 << idx; 455 } 456 size_t num_no_null_ck = 0u; 457 for (size_t i = 0; i != mir_count_; ++i) { 458 if ((mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) { 459 ++num_no_null_ck; 460 } 461 } 462 EXPECT_EQ(count, num_no_null_ck); 463 } 464 465 GvnDeadCodeEliminationTest() 466 : pool_(), 467 cu_(&pool_, kRuntimeISA, nullptr, nullptr), 468 num_vregs_(0u), 469 mir_count_(0u), 470 mirs_(nullptr), 471 ssa_reps_(), 472 allocator_(), 473 gvn_(), 474 dce_(), 475 value_names_(), 476 live_in_v_(new (&cu_.arena) ArenaBitVector(&cu_.arena, kMaxSsaRegs, false, kBitMapMisc)) { 477 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena)); 478 cu_.access_flags = kAccStatic; // Don't let "this" interfere with this test. 479 allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack)); 480 // By default, the zero-initialized reg_location_[.] with ref == false tells LVN that 481 // 0 constants are integral, not references, and the values are all narrow. 482 // Nothing else is used by LVN/GVN. Tests can override the default values as needed. 483 cu_.mir_graph->reg_location_ = static_cast<RegLocation*>(cu_.arena.Alloc( 484 kMaxSsaRegs * sizeof(cu_.mir_graph->reg_location_[0]), kArenaAllocRegAlloc)); 485 cu_.mir_graph->num_ssa_regs_ = kMaxSsaRegs; 486 // Bind all possible sregs to live vregs for test purposes. 487 live_in_v_->SetInitialBits(kMaxSsaRegs); 488 cu_.mir_graph->ssa_base_vregs_.reserve(kMaxSsaRegs); 489 cu_.mir_graph->ssa_subscripts_.reserve(kMaxSsaRegs); 490 for (unsigned int i = 0; i < kMaxSsaRegs; i++) { 491 cu_.mir_graph->ssa_base_vregs_.push_back(i); 492 cu_.mir_graph->ssa_subscripts_.push_back(0); 493 } 494 // Set shorty for a void-returning method without arguments. 495 cu_.shorty = "V"; 496 } 497 498 static constexpr size_t kMaxSsaRegs = 16384u; 499 static constexpr size_t kMaxVRegs = 256u; 500 501 ArenaPool pool_; 502 CompilationUnit cu_; 503 size_t num_vregs_; 504 size_t mir_count_; 505 MIR* mirs_; 506 std::vector<SSARepresentation> ssa_reps_; 507 std::unique_ptr<ScopedArenaAllocator> allocator_; 508 std::unique_ptr<GlobalValueNumbering> gvn_; 509 std::unique_ptr<GvnDeadCodeElimination> dce_; 510 std::vector<uint16_t> value_names_; 511 ArenaBitVector* live_in_v_; 512 }; 513 514 constexpr uint16_t GvnDeadCodeEliminationTest::kNoValue; 515 516 class GvnDeadCodeEliminationTestSimple : public GvnDeadCodeEliminationTest { 517 public: 518 GvnDeadCodeEliminationTestSimple(); 519 520 private: 521 static const BBDef kSimpleBbs[]; 522 }; 523 524 const GvnDeadCodeEliminationTest::BBDef GvnDeadCodeEliminationTestSimple::kSimpleBbs[] = { 525 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 526 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 527 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(3)), 528 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(1)), 529 }; 530 531 GvnDeadCodeEliminationTestSimple::GvnDeadCodeEliminationTestSimple() 532 : GvnDeadCodeEliminationTest() { 533 PrepareBasicBlocks(kSimpleBbs); 534 } 535 536 class GvnDeadCodeEliminationTestDiamond : public GvnDeadCodeEliminationTest { 537 public: 538 GvnDeadCodeEliminationTestDiamond(); 539 540 private: 541 static const BBDef kDiamondBbs[]; 542 }; 543 544 const GvnDeadCodeEliminationTest::BBDef GvnDeadCodeEliminationTestDiamond::kDiamondBbs[] = { 545 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 546 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 547 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)), 548 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // Block #3, top of the diamond. 549 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #4, left side. 550 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #5, right side. 551 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // Block #6, bottom. 552 }; 553 554 GvnDeadCodeEliminationTestDiamond::GvnDeadCodeEliminationTestDiamond() 555 : GvnDeadCodeEliminationTest() { 556 PrepareBasicBlocks(kDiamondBbs); 557 } 558 559 class GvnDeadCodeEliminationTestLoop : public GvnDeadCodeEliminationTest { 560 public: 561 GvnDeadCodeEliminationTestLoop(); 562 563 private: 564 static const BBDef kLoopBbs[]; 565 }; 566 567 const GvnDeadCodeEliminationTest::BBDef GvnDeadCodeEliminationTestLoop::kLoopBbs[] = { 568 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()), 569 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()), 570 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)), 571 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), 572 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)), // "taken" loops to self. 573 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)), 574 }; 575 576 GvnDeadCodeEliminationTestLoop::GvnDeadCodeEliminationTestLoop() 577 : GvnDeadCodeEliminationTest() { 578 PrepareBasicBlocks(kLoopBbs); 579 } 580 581 TEST_F(GvnDeadCodeEliminationTestSimple, Rename1) { 582 static const IFieldDef ifields[] = { 583 { 0u, 1u, 0u, false, kDexMemAccessWord }, 584 { 1u, 1u, 1u, false, kDexMemAccessWord }, 585 }; 586 static const MIRDef mirs[] = { 587 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 588 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 589 DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 0u), 590 DEF_IGET(3, Instruction::IGET, 3u, 2u, 1u), 591 }; 592 593 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 2 }; 594 PrepareSRegToVRegMap(sreg_to_vreg_map); 595 596 PrepareIFields(ifields); 597 PrepareMIRs(mirs); 598 PerformGVN_DCE(); 599 600 ASSERT_EQ(arraysize(mirs), value_names_.size()); 601 static const size_t diff_indexes[] = { 0, 1, 3 }; 602 ExpectValueNamesNE(diff_indexes); 603 EXPECT_EQ(value_names_[0], value_names_[2]); 604 605 const size_t no_null_ck_indexes[] = { 1, 3 }; 606 ExpectNoNullCheck(no_null_ck_indexes); 607 608 static const bool eliminated[] = { 609 false, false, true, false 610 }; 611 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 612 for (size_t i = 0; i != arraysize(eliminated); ++i) { 613 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 614 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 615 } 616 // Check that the IGET uses the s_reg 0, v_reg 0, defined by mirs_[0]. 617 ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses); 618 EXPECT_EQ(0, mirs_[3].ssa_rep->uses[0]); 619 EXPECT_EQ(0u, mirs_[3].dalvikInsn.vB); 620 } 621 622 TEST_F(GvnDeadCodeEliminationTestSimple, Rename2) { 623 static const IFieldDef ifields[] = { 624 { 0u, 1u, 0u, false, kDexMemAccessWord }, 625 { 1u, 1u, 1u, false, kDexMemAccessWord }, 626 }; 627 static const MIRDef mirs[] = { 628 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 629 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 630 DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 0u), 631 DEF_IGET(3, Instruction::IGET, 3u, 2u, 1u), 632 DEF_CONST(3, Instruction::CONST, 4u, 1000), 633 }; 634 635 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 2 }; 636 PrepareSRegToVRegMap(sreg_to_vreg_map); 637 638 PrepareIFields(ifields); 639 PrepareMIRs(mirs); 640 PerformGVN_DCE(); 641 642 ASSERT_EQ(arraysize(mirs), value_names_.size()); 643 static const size_t diff_indexes[] = { 0, 1, 3, 4 }; 644 ExpectValueNamesNE(diff_indexes); 645 EXPECT_EQ(value_names_[0], value_names_[2]); 646 647 const size_t no_null_ck_indexes[] = { 1, 3 }; 648 ExpectNoNullCheck(no_null_ck_indexes); 649 650 static const bool eliminated[] = { 651 false, false, true, false, false 652 }; 653 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 654 for (size_t i = 0; i != arraysize(eliminated); ++i) { 655 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 656 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 657 } 658 // Check that the IGET uses the s_reg 0, v_reg 0, defined by mirs_[0]. 659 ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses); 660 EXPECT_EQ(0, mirs_[3].ssa_rep->uses[0]); 661 EXPECT_EQ(0u, mirs_[3].dalvikInsn.vB); 662 } 663 664 TEST_F(GvnDeadCodeEliminationTestSimple, Rename3) { 665 static const IFieldDef ifields[] = { 666 { 0u, 1u, 0u, false, kDexMemAccessWord }, 667 { 1u, 1u, 1u, false, kDexMemAccessWord }, 668 }; 669 static const MIRDef mirs[] = { 670 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 671 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 672 DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 0u), 673 DEF_IGET(3, Instruction::IGET, 3u, 2u, 1u), 674 }; 675 676 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 0 }; 677 PrepareSRegToVRegMap(sreg_to_vreg_map); 678 679 PrepareIFields(ifields); 680 PrepareMIRs(mirs); 681 PerformGVN_DCE(); 682 683 ASSERT_EQ(arraysize(mirs), value_names_.size()); 684 static const size_t diff_indexes[] = { 0, 1, 3 }; 685 ExpectValueNamesNE(diff_indexes); 686 EXPECT_EQ(value_names_[0], value_names_[2]); 687 688 const size_t no_null_ck_indexes[] = { 1, 3 }; 689 ExpectNoNullCheck(no_null_ck_indexes); 690 691 static const bool eliminated[] = { 692 false, false, true, false 693 }; 694 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 695 for (size_t i = 0; i != arraysize(eliminated); ++i) { 696 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 697 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 698 } 699 // Check that the NEW_INSTANCE defines the s_reg 2, v_reg 2, originally defined by the move. 700 ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs); 701 EXPECT_EQ(2, mirs_[0].ssa_rep->defs[0]); 702 EXPECT_EQ(2u, mirs_[0].dalvikInsn.vA); 703 // Check that the first IGET is using the s_reg 2, v_reg 2. 704 ASSERT_EQ(1, mirs_[1].ssa_rep->num_uses); 705 EXPECT_EQ(2, mirs_[1].ssa_rep->uses[0]); 706 EXPECT_EQ(2u, mirs_[1].dalvikInsn.vB); 707 } 708 709 TEST_F(GvnDeadCodeEliminationTestSimple, Rename4) { 710 static const MIRDef mirs[] = { 711 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 712 DEF_MOVE(3, Instruction::MOVE_OBJECT, 1u, 0u), 713 DEF_MOVE(3, Instruction::MOVE_OBJECT, 2u, 1u), 714 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 3u, 1000u), 715 }; 716 717 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 0, 1 /* high word */ }; 718 PrepareSRegToVRegMap(sreg_to_vreg_map); 719 720 PrepareMIRs(mirs); 721 static const int32_t wide_sregs[] = { 3 }; 722 MarkAsWideSRegs(wide_sregs); 723 PerformGVN_DCE(); 724 725 ASSERT_EQ(arraysize(mirs), value_names_.size()); 726 static const size_t diff_indexes[] = { 0, 3 }; 727 ExpectValueNamesNE(diff_indexes); 728 EXPECT_EQ(value_names_[0], value_names_[1]); 729 EXPECT_EQ(value_names_[0], value_names_[2]); 730 731 static const bool eliminated[] = { 732 false, true, true, false 733 }; 734 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 735 for (size_t i = 0; i != arraysize(eliminated); ++i) { 736 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 737 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 738 } 739 // Check that the NEW_INSTANCE defines the s_reg 2, v_reg 2, originally defined by the move 2u. 740 ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs); 741 EXPECT_EQ(2, mirs_[0].ssa_rep->defs[0]); 742 EXPECT_EQ(2u, mirs_[0].dalvikInsn.vA); 743 } 744 745 TEST_F(GvnDeadCodeEliminationTestSimple, Rename5) { 746 static const IFieldDef ifields[] = { 747 { 0u, 1u, 0u, false, kDexMemAccessWord }, 748 }; 749 static const MIRDef mirs[] = { 750 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 751 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 752 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 2u, 1u), 753 DEF_MOVE(3, Instruction::MOVE_OBJECT, 3u, 0u), 754 DEF_MOVE(3, Instruction::MOVE_OBJECT, 4u, 3u), 755 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 5u, 1000u), 756 }; 757 758 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 3, 0, 1 /* high word */ }; 759 PrepareSRegToVRegMap(sreg_to_vreg_map); 760 761 PrepareIFields(ifields); 762 PrepareMIRs(mirs); 763 static const int32_t wide_sregs[] = { 5 }; 764 MarkAsWideSRegs(wide_sregs); 765 PerformGVN_DCE(); 766 767 ASSERT_EQ(arraysize(mirs), value_names_.size()); 768 static const size_t diff_indexes[] = { 0, 1, 2, 5 }; 769 ExpectValueNamesNE(diff_indexes); 770 EXPECT_EQ(value_names_[0], value_names_[3]); 771 EXPECT_EQ(value_names_[0], value_names_[4]); 772 773 static const bool eliminated[] = { 774 false, false, false, true, true, false 775 }; 776 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 777 for (size_t i = 0; i != arraysize(eliminated); ++i) { 778 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 779 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 780 } 781 // Check that the NEW_INSTANCE defines the s_reg 4, v_reg 3, originally defined by the move 4u. 782 ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs); 783 EXPECT_EQ(4, mirs_[0].ssa_rep->defs[0]); 784 EXPECT_EQ(3u, mirs_[0].dalvikInsn.vA); 785 } 786 787 TEST_F(GvnDeadCodeEliminationTestSimple, Rename6) { 788 static const MIRDef mirs[] = { 789 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u), 790 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 2u, 0u), 791 }; 792 793 static const int32_t sreg_to_vreg_map[] = { 0, 1 /* high word */, 1, 2 /* high word */ }; 794 PrepareSRegToVRegMap(sreg_to_vreg_map); 795 796 PrepareMIRs(mirs); 797 static const int32_t wide_sregs[] = { 0, 2 }; 798 MarkAsWideSRegs(wide_sregs); 799 PerformGVN_DCE(); 800 801 ASSERT_EQ(arraysize(mirs), value_names_.size()); 802 EXPECT_EQ(value_names_[0], value_names_[1]); 803 804 static const bool eliminated[] = { 805 false, true 806 }; 807 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 808 for (size_t i = 0; i != arraysize(eliminated); ++i) { 809 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 810 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 811 } 812 // Check that the CONST_WIDE defines the s_reg 2, v_reg 1, originally defined by the move 2u. 813 ASSERT_EQ(2, mirs_[0].ssa_rep->num_defs); 814 EXPECT_EQ(2, mirs_[0].ssa_rep->defs[0]); 815 EXPECT_EQ(3, mirs_[0].ssa_rep->defs[1]); 816 EXPECT_EQ(1u, mirs_[0].dalvikInsn.vA); 817 } 818 819 TEST_F(GvnDeadCodeEliminationTestSimple, Rename7) { 820 static const MIRDef mirs[] = { 821 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 822 DEF_MOVE(3, Instruction::MOVE, 1u, 0u), 823 DEF_BINOP(3, Instruction::ADD_INT, 2u, 0u, 1u), 824 }; 825 826 static const int32_t sreg_to_vreg_map[] = { 0, 1, 0 }; 827 PrepareSRegToVRegMap(sreg_to_vreg_map); 828 829 PrepareMIRs(mirs); 830 PerformGVN_DCE(); 831 832 ASSERT_EQ(arraysize(mirs), value_names_.size()); 833 EXPECT_NE(value_names_[0], value_names_[2]); 834 EXPECT_EQ(value_names_[0], value_names_[1]); 835 836 static const bool eliminated[] = { 837 false, true, false 838 }; 839 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 840 for (size_t i = 0; i != arraysize(eliminated); ++i) { 841 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 842 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 843 } 844 // Check that the CONST defines the s_reg 1, v_reg 1, originally defined by the move 1u. 845 ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs); 846 EXPECT_EQ(1, mirs_[0].ssa_rep->defs[0]); 847 EXPECT_EQ(1u, mirs_[0].dalvikInsn.vA); 848 // Check that the ADD_INT inputs are both s_reg1, vreg 1. 849 ASSERT_EQ(2, mirs_[2].ssa_rep->num_uses); 850 EXPECT_EQ(1, mirs_[2].ssa_rep->uses[0]); 851 EXPECT_EQ(1, mirs_[2].ssa_rep->uses[1]); 852 EXPECT_EQ(1u, mirs_[2].dalvikInsn.vB); 853 EXPECT_EQ(1u, mirs_[2].dalvikInsn.vC); 854 } 855 856 TEST_F(GvnDeadCodeEliminationTestSimple, Rename8) { 857 static const MIRDef mirs[] = { 858 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 859 DEF_MOVE(3, Instruction::MOVE, 1u, 0u), 860 DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 2u, 0u, 1u), 861 }; 862 863 static const int32_t sreg_to_vreg_map[] = { 0, 1, 0 }; 864 PrepareSRegToVRegMap(sreg_to_vreg_map); 865 866 PrepareMIRs(mirs); 867 PerformGVN_DCE(); 868 869 ASSERT_EQ(arraysize(mirs), value_names_.size()); 870 EXPECT_NE(value_names_[0], value_names_[2]); 871 EXPECT_EQ(value_names_[0], value_names_[1]); 872 873 static const bool eliminated[] = { 874 false, true, false 875 }; 876 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 877 for (size_t i = 0; i != arraysize(eliminated); ++i) { 878 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 879 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 880 } 881 // Check that the CONST defines the s_reg 1, v_reg 1, originally defined by the move 1u. 882 ASSERT_EQ(1, mirs_[0].ssa_rep->num_defs); 883 EXPECT_EQ(1, mirs_[0].ssa_rep->defs[0]); 884 EXPECT_EQ(1u, mirs_[0].dalvikInsn.vA); 885 // Check that the ADD_INT_2ADDR was replaced by ADD_INT and inputs are both s_reg 1, vreg 1. 886 EXPECT_EQ(Instruction::ADD_INT, mirs_[2].dalvikInsn.opcode); 887 ASSERT_EQ(2, mirs_[2].ssa_rep->num_uses); 888 EXPECT_EQ(1, mirs_[2].ssa_rep->uses[0]); 889 EXPECT_EQ(1, mirs_[2].ssa_rep->uses[1]); 890 EXPECT_EQ(1u, mirs_[2].dalvikInsn.vB); 891 EXPECT_EQ(1u, mirs_[2].dalvikInsn.vC); 892 } 893 894 TEST_F(GvnDeadCodeEliminationTestSimple, Rename9) { 895 static const MIRDef mirs[] = { 896 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 897 DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 1u, 0u, 0u), 898 DEF_MOVE(3, Instruction::MOVE, 2u, 1u), 899 DEF_CONST(3, Instruction::CONST, 3u, 3000u), 900 }; 901 902 static const int32_t sreg_to_vreg_map[] = { 0, 0, 1, 0 }; 903 PrepareSRegToVRegMap(sreg_to_vreg_map); 904 905 PrepareMIRs(mirs); 906 PerformGVN_DCE(); 907 908 ASSERT_EQ(arraysize(mirs), value_names_.size()); 909 static const size_t diff_indexes[] = { 0, 1, 3 }; 910 ExpectValueNamesNE(diff_indexes); 911 EXPECT_EQ(value_names_[1], value_names_[2]); 912 913 static const bool eliminated[] = { 914 false, false, true, false 915 }; 916 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 917 for (size_t i = 0; i != arraysize(eliminated); ++i) { 918 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 919 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 920 } 921 // Check that the ADD_INT_2ADDR was replaced by ADD_INT and output is in s_reg 2, vreg 1. 922 EXPECT_EQ(Instruction::ADD_INT, mirs_[1].dalvikInsn.opcode); 923 ASSERT_EQ(2, mirs_[1].ssa_rep->num_uses); 924 EXPECT_EQ(0, mirs_[1].ssa_rep->uses[0]); 925 EXPECT_EQ(0, mirs_[1].ssa_rep->uses[1]); 926 EXPECT_EQ(0u, mirs_[1].dalvikInsn.vB); 927 EXPECT_EQ(0u, mirs_[1].dalvikInsn.vC); 928 ASSERT_EQ(1, mirs_[1].ssa_rep->num_defs); 929 EXPECT_EQ(2, mirs_[1].ssa_rep->defs[0]); 930 EXPECT_EQ(1u, mirs_[1].dalvikInsn.vA); 931 } 932 933 TEST_F(GvnDeadCodeEliminationTestSimple, NoRename1) { 934 static const IFieldDef ifields[] = { 935 { 0u, 1u, 0u, false, kDexMemAccessWord }, 936 { 1u, 1u, 1u, false, kDexMemAccessWord }, 937 }; 938 static const MIRDef mirs[] = { 939 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 940 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 941 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 2u, 1u), 942 DEF_MOVE(3, Instruction::MOVE_OBJECT, 3u, 0u), 943 DEF_CONST(3, Instruction::CONST, 4u, 1000), 944 DEF_IGET(3, Instruction::IGET, 5u, 3u, 1u), 945 }; 946 947 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 0, 1 }; 948 PrepareSRegToVRegMap(sreg_to_vreg_map); 949 950 PrepareIFields(ifields); 951 PrepareMIRs(mirs); 952 PerformGVN_DCE(); 953 954 ASSERT_EQ(arraysize(mirs), value_names_.size()); 955 static const size_t diff_indexes[] = { 0, 1, 2, 4, 5 }; 956 ExpectValueNamesNE(diff_indexes); 957 EXPECT_EQ(value_names_[0], value_names_[3]); 958 959 const size_t no_null_ck_indexes[] = { 1, 5 }; 960 ExpectNoNullCheck(no_null_ck_indexes); 961 962 static const bool eliminated[] = { 963 false, false, false, false, false, false 964 }; 965 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 966 for (size_t i = 0; i != arraysize(eliminated); ++i) { 967 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 968 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 969 } 970 } 971 972 TEST_F(GvnDeadCodeEliminationTestSimple, NoRename2) { 973 static const IFieldDef ifields[] = { 974 { 0u, 1u, 0u, false, kDexMemAccessWord }, 975 { 1u, 1u, 1u, false, kDexMemAccessWord }, 976 }; 977 static const MIRDef mirs[] = { 978 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 979 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 980 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 2u), 981 DEF_MOVE(3, Instruction::MOVE_OBJECT, 3u, 0u), 982 DEF_CONST(3, Instruction::CONST, 4u, 1000), 983 DEF_IGET(3, Instruction::IGET, 5u, 3u, 1u), 984 DEF_CONST(3, Instruction::CONST, 6u, 2000), 985 }; 986 987 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 2, 0, 3, 2 }; 988 PrepareSRegToVRegMap(sreg_to_vreg_map); 989 990 PrepareIFields(ifields); 991 PrepareMIRs(mirs); 992 PerformGVN_DCE(); 993 994 ASSERT_EQ(arraysize(mirs), value_names_.size()); 995 static const size_t diff_indexes[] = { 0, 1, 2, 4, 5, 6 }; 996 ExpectValueNamesNE(diff_indexes); 997 EXPECT_EQ(value_names_[0], value_names_[3]); 998 999 const size_t no_null_ck_indexes[] = { 1, 5 }; 1000 ExpectNoNullCheck(no_null_ck_indexes); 1001 1002 static const bool eliminated[] = { 1003 false, false, false, false, false, false, false 1004 }; 1005 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1006 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1007 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1008 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1009 } 1010 } 1011 1012 TEST_F(GvnDeadCodeEliminationTestSimple, NoRename3) { 1013 static const IFieldDef ifields[] = { 1014 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1015 { 1u, 1u, 1u, false, kDexMemAccessWord }, 1016 { 2u, 1u, 2u, false, kDexMemAccessWord }, 1017 }; 1018 static const MIRDef mirs[] = { 1019 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1020 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u), 1021 DEF_IGET(3, Instruction::IGET, 2u, 0u, 2u), 1022 DEF_BINOP(3, Instruction::ADD_INT, 3u, 1u, 2u), 1023 DEF_MOVE(3, Instruction::MOVE_OBJECT, 4u, 0u), 1024 DEF_IGET(3, Instruction::IGET, 5u, 4u, 1u), 1025 }; 1026 1027 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 2, 0 }; 1028 PrepareSRegToVRegMap(sreg_to_vreg_map); 1029 1030 PrepareIFields(ifields); 1031 PrepareMIRs(mirs); 1032 PerformGVN_DCE(); 1033 1034 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1035 static const size_t diff_indexes[] = { 0, 1, 2, 3, 5 }; 1036 ExpectValueNamesNE(diff_indexes); 1037 EXPECT_EQ(value_names_[0], value_names_[4]); 1038 1039 const size_t no_null_ck_indexes[] = { 1, 2, 5 }; 1040 ExpectNoNullCheck(no_null_ck_indexes); 1041 1042 static const bool eliminated[] = { 1043 false, false, false, false, false, false 1044 }; 1045 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1046 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1047 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1048 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1049 } 1050 } 1051 1052 TEST_F(GvnDeadCodeEliminationTestSimple, NoRename4) { 1053 static const MIRDef mirs[] = { 1054 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 1055 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 1u), 1056 DEF_CONST(3, Instruction::CONST, 2u, 100u), 1057 DEF_CONST(3, Instruction::CONST, 3u, 200u), 1058 DEF_BINOP(3, Instruction::OR_INT_2ADDR, 4u, 2u, 3u), // 3. Find definition of the move src. 1059 DEF_MOVE(3, Instruction::MOVE, 5u, 0u), // 4. Uses move dest vreg. 1060 DEF_MOVE(3, Instruction::MOVE, 6u, 4u), // 2. Find overwritten move src. 1061 DEF_CONST(3, Instruction::CONST, 7u, 2000u), // 1. Overwrites 4u, look for moves. 1062 }; 1063 1064 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 2, 4, 0, 2 }; 1065 PrepareSRegToVRegMap(sreg_to_vreg_map); 1066 1067 PrepareMIRs(mirs); 1068 PerformGVN_DCE(); 1069 1070 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1071 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 7 }; 1072 ExpectValueNamesNE(diff_indexes); 1073 EXPECT_EQ(value_names_[0], value_names_[5]); 1074 EXPECT_EQ(value_names_[4], value_names_[6]); 1075 1076 static const bool eliminated[] = { 1077 false, false, false, false, false, false, false, false 1078 }; 1079 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1080 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1081 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1082 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1083 } 1084 } 1085 1086 TEST_F(GvnDeadCodeEliminationTestSimple, Simple1) { 1087 static const IFieldDef ifields[] = { 1088 { 0u, 1u, 0u, false, kDexMemAccessObject }, 1089 { 1u, 1u, 1u, false, kDexMemAccessObject }, 1090 { 2u, 1u, 2u, false, kDexMemAccessWord }, 1091 }; 1092 static const MIRDef mirs[] = { 1093 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1094 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 0u, 0u), 1095 DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 1u, 1u), 1096 DEF_IGET(3, Instruction::IGET, 3u, 2u, 2u), 1097 DEF_IGET(3, Instruction::IGET_OBJECT, 4u, 0u, 0u), 1098 DEF_IGET(3, Instruction::IGET_OBJECT, 5u, 4u, 1u), 1099 }; 1100 1101 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 1, 2 }; 1102 PrepareSRegToVRegMap(sreg_to_vreg_map); 1103 1104 PrepareIFields(ifields); 1105 PrepareMIRs(mirs); 1106 PerformGVN_DCE(); 1107 1108 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1109 EXPECT_NE(value_names_[0], value_names_[1]); 1110 EXPECT_NE(value_names_[0], value_names_[2]); 1111 EXPECT_NE(value_names_[0], value_names_[3]); 1112 EXPECT_NE(value_names_[1], value_names_[2]); 1113 EXPECT_NE(value_names_[1], value_names_[3]); 1114 EXPECT_NE(value_names_[2], value_names_[3]); 1115 EXPECT_EQ(value_names_[1], value_names_[4]); 1116 EXPECT_EQ(value_names_[2], value_names_[5]); 1117 1118 EXPECT_EQ(MIR_IGNORE_NULL_CHECK, mirs_[4].optimization_flags & MIR_IGNORE_NULL_CHECK); 1119 EXPECT_EQ(MIR_IGNORE_NULL_CHECK, mirs_[5].optimization_flags & MIR_IGNORE_NULL_CHECK); 1120 1121 static const bool eliminated[] = { 1122 false, false, false, false, true, true 1123 }; 1124 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1125 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1126 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1127 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1128 } 1129 // Check that the sregs have been renamed correctly. 1130 ASSERT_EQ(1, mirs_[1].ssa_rep->num_defs); 1131 EXPECT_EQ(4, mirs_[1].ssa_rep->defs[0]); 1132 ASSERT_EQ(1, mirs_[1].ssa_rep->num_uses); 1133 EXPECT_EQ(0, mirs_[1].ssa_rep->uses[0]); 1134 ASSERT_EQ(1, mirs_[2].ssa_rep->num_defs); 1135 EXPECT_EQ(5, mirs_[2].ssa_rep->defs[0]); 1136 ASSERT_EQ(1, mirs_[2].ssa_rep->num_uses); 1137 EXPECT_EQ(4, mirs_[2].ssa_rep->uses[0]); 1138 ASSERT_EQ(1, mirs_[3].ssa_rep->num_defs); 1139 EXPECT_EQ(3, mirs_[3].ssa_rep->defs[0]); 1140 ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses); 1141 EXPECT_EQ(5, mirs_[3].ssa_rep->uses[0]); 1142 } 1143 1144 TEST_F(GvnDeadCodeEliminationTestSimple, Simple2) { 1145 static const IFieldDef ifields[] = { 1146 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1147 }; 1148 static const MIRDef mirs[] = { 1149 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1150 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1151 DEF_IGET(3, Instruction::IGET, 2u, 0u, 0u), 1152 DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 3u, 2u, 1u), 1153 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 4u, 3u), 1154 DEF_IGET(3, Instruction::IGET, 5u, 0u, 0u), 1155 DEF_BINOP(3, Instruction::ADD_INT_2ADDR, 6u, 5u, 1u), 1156 }; 1157 1158 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 2, 3, 2, 2 }; 1159 PrepareSRegToVRegMap(sreg_to_vreg_map); 1160 1161 PrepareIFields(ifields); 1162 PrepareMIRs(mirs); 1163 PerformGVN_DCE(); 1164 1165 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1166 static const size_t diff_indexes[] = { 0, 1, 2, 3 }; 1167 ExpectValueNamesNE(diff_indexes); 1168 EXPECT_EQ(value_names_[2], value_names_[5]); 1169 EXPECT_EQ(value_names_[3], value_names_[6]); 1170 1171 const size_t no_null_ck_indexes[] = { 2, 5 }; 1172 ExpectNoNullCheck(no_null_ck_indexes); 1173 1174 static const bool eliminated[] = { 1175 false, false, false, false, false, true, true 1176 }; 1177 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1178 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1179 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1180 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1181 } 1182 // Check that the sregs have been renamed correctly. 1183 ASSERT_EQ(1, mirs_[3].ssa_rep->num_defs); 1184 EXPECT_EQ(6, mirs_[3].ssa_rep->defs[0]); 1185 ASSERT_EQ(2, mirs_[3].ssa_rep->num_uses); 1186 EXPECT_EQ(2, mirs_[3].ssa_rep->uses[0]); 1187 EXPECT_EQ(1, mirs_[3].ssa_rep->uses[1]); 1188 ASSERT_EQ(1, mirs_[4].ssa_rep->num_defs); 1189 EXPECT_EQ(4, mirs_[4].ssa_rep->defs[0]); 1190 ASSERT_EQ(1, mirs_[4].ssa_rep->num_uses); 1191 EXPECT_EQ(6, mirs_[4].ssa_rep->uses[0]); 1192 } 1193 1194 TEST_F(GvnDeadCodeEliminationTestSimple, Simple3) { 1195 static const IFieldDef ifields[] = { 1196 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1197 }; 1198 static const MIRDef mirs[] = { 1199 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1200 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1201 DEF_CONST(3, Instruction::CONST, 2u, 2000), 1202 DEF_CONST(3, Instruction::CONST, 3u, 3000), 1203 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1204 DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u), 1205 DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u), 1206 DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u), 1207 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u), 1208 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1209 DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u), 1210 DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u), // Simple elimination of ADD+MUL 1211 DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u), // allows simple elimination of IGET+SUB. 1212 }; 1213 1214 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 5, 5, 4 }; 1215 PrepareSRegToVRegMap(sreg_to_vreg_map); 1216 1217 PrepareIFields(ifields); 1218 PrepareMIRs(mirs); 1219 PerformGVN_DCE(); 1220 1221 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1222 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; 1223 ExpectValueNamesNE(diff_indexes); 1224 EXPECT_EQ(value_names_[4], value_names_[9]); 1225 EXPECT_EQ(value_names_[5], value_names_[10]); 1226 EXPECT_EQ(value_names_[6], value_names_[11]); 1227 EXPECT_EQ(value_names_[7], value_names_[12]); 1228 1229 const size_t no_null_ck_indexes[] = { 4, 9 }; 1230 ExpectNoNullCheck(no_null_ck_indexes); 1231 1232 static const bool eliminated[] = { 1233 false, false, false, false, false, false, false, false, false, true, true, true, true 1234 }; 1235 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1236 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1237 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1238 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1239 } 1240 // Check that the sregs have been renamed correctly. 1241 ASSERT_EQ(1, mirs_[6].ssa_rep->num_defs); 1242 EXPECT_EQ(11, mirs_[6].ssa_rep->defs[0]); // 6 -> 11 1243 ASSERT_EQ(2, mirs_[6].ssa_rep->num_uses); 1244 EXPECT_EQ(5, mirs_[6].ssa_rep->uses[0]); 1245 EXPECT_EQ(2, mirs_[6].ssa_rep->uses[1]); 1246 ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs); 1247 EXPECT_EQ(12, mirs_[7].ssa_rep->defs[0]); // 7 -> 12 1248 ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses); 1249 EXPECT_EQ(11, mirs_[7].ssa_rep->uses[0]); // 6 -> 11 1250 EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]); 1251 ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs); 1252 EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]); 1253 ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses); 1254 EXPECT_EQ(12, mirs_[8].ssa_rep->uses[0]); // 7 -> 12 1255 } 1256 1257 TEST_F(GvnDeadCodeEliminationTestSimple, Simple4) { 1258 static const IFieldDef ifields[] = { 1259 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1260 }; 1261 static const MIRDef mirs[] = { 1262 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1263 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 1u, INT64_C(1)), 1264 DEF_BINOP(3, Instruction::LONG_TO_FLOAT, 3u, 1u, 2u), 1265 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1266 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 5u, 4u), 1267 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 6u, INT64_C(1)), 1268 DEF_BINOP(3, Instruction::LONG_TO_FLOAT, 8u, 6u, 7u), 1269 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1270 }; 1271 1272 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 2, 3, 1, 2, 1, 2 }; 1273 PrepareSRegToVRegMap(sreg_to_vreg_map); 1274 1275 PrepareIFields(ifields); 1276 PrepareMIRs(mirs); 1277 static const int32_t wide_sregs[] = { 1, 6 }; 1278 MarkAsWideSRegs(wide_sregs); 1279 PerformGVN_DCE(); 1280 1281 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1282 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4 }; 1283 ExpectValueNamesNE(diff_indexes); 1284 EXPECT_EQ(value_names_[1], value_names_[5]); 1285 EXPECT_EQ(value_names_[2], value_names_[6]); 1286 EXPECT_EQ(value_names_[3], value_names_[7]); 1287 1288 const size_t no_null_ck_indexes[] = { 3, 7 }; 1289 ExpectNoNullCheck(no_null_ck_indexes); 1290 1291 static const bool eliminated[] = { 1292 // Simple elimination of CONST_WIDE+LONG_TO_FLOAT allows simple eliminatiion of IGET. 1293 false, false, false, false, false, true, true, true 1294 }; 1295 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1296 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1297 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1298 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1299 } 1300 // Check that the sregs have been renamed correctly. 1301 ASSERT_EQ(1, mirs_[2].ssa_rep->num_defs); 1302 EXPECT_EQ(8, mirs_[2].ssa_rep->defs[0]); // 3 -> 8 1303 ASSERT_EQ(2, mirs_[2].ssa_rep->num_uses); 1304 EXPECT_EQ(1, mirs_[2].ssa_rep->uses[0]); 1305 EXPECT_EQ(2, mirs_[2].ssa_rep->uses[1]); 1306 ASSERT_EQ(1, mirs_[3].ssa_rep->num_defs); 1307 EXPECT_EQ(9, mirs_[3].ssa_rep->defs[0]); // 4 -> 9 1308 ASSERT_EQ(1, mirs_[3].ssa_rep->num_uses); 1309 EXPECT_EQ(0, mirs_[3].ssa_rep->uses[0]); 1310 ASSERT_EQ(1, mirs_[4].ssa_rep->num_defs); 1311 EXPECT_EQ(5, mirs_[4].ssa_rep->defs[0]); 1312 ASSERT_EQ(1, mirs_[4].ssa_rep->num_uses); 1313 EXPECT_EQ(9, mirs_[4].ssa_rep->uses[0]); // 4 -> 9 1314 } 1315 1316 TEST_F(GvnDeadCodeEliminationTestSimple, KillChain1) { 1317 static const IFieldDef ifields[] = { 1318 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1319 }; 1320 static const MIRDef mirs[] = { 1321 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1322 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1323 DEF_CONST(3, Instruction::CONST, 2u, 2000), 1324 DEF_CONST(3, Instruction::CONST, 3u, 3000), 1325 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1326 DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u), 1327 DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u), 1328 DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u), 1329 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u), 1330 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1331 DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u), 1332 DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u), 1333 DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u), 1334 }; 1335 1336 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 4, 5, 6, 4, 5, 4, 5 }; 1337 PrepareSRegToVRegMap(sreg_to_vreg_map); 1338 1339 PrepareIFields(ifields); 1340 PrepareMIRs(mirs); 1341 PerformGVN_DCE(); 1342 1343 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1344 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; 1345 ExpectValueNamesNE(diff_indexes); 1346 EXPECT_EQ(value_names_[4], value_names_[9]); 1347 EXPECT_EQ(value_names_[5], value_names_[10]); 1348 EXPECT_EQ(value_names_[6], value_names_[11]); 1349 EXPECT_EQ(value_names_[7], value_names_[12]); 1350 1351 const size_t no_null_ck_indexes[] = { 4, 9 }; 1352 ExpectNoNullCheck(no_null_ck_indexes); 1353 1354 static const bool eliminated[] = { 1355 false, false, false, false, false, false, false, false, false, true, true, true, true 1356 }; 1357 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1358 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1359 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1360 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1361 } 1362 // Check that the sregs have been renamed correctly. 1363 ASSERT_EQ(1, mirs_[6].ssa_rep->num_defs); 1364 EXPECT_EQ(11, mirs_[6].ssa_rep->defs[0]); // 6 -> 11 1365 ASSERT_EQ(2, mirs_[6].ssa_rep->num_uses); 1366 EXPECT_EQ(5, mirs_[6].ssa_rep->uses[0]); 1367 EXPECT_EQ(2, mirs_[6].ssa_rep->uses[1]); 1368 ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs); 1369 EXPECT_EQ(12, mirs_[7].ssa_rep->defs[0]); // 7 -> 12 1370 ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses); 1371 EXPECT_EQ(11, mirs_[7].ssa_rep->uses[0]); // 6 -> 11 1372 EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]); 1373 ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs); 1374 EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]); 1375 ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses); 1376 EXPECT_EQ(12, mirs_[8].ssa_rep->uses[0]); // 7 -> 12 1377 } 1378 1379 TEST_F(GvnDeadCodeEliminationTestSimple, KillChain2) { 1380 static const IFieldDef ifields[] = { 1381 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1382 }; 1383 static const MIRDef mirs[] = { 1384 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1385 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1386 DEF_CONST(3, Instruction::CONST, 2u, 2000), 1387 DEF_CONST(3, Instruction::CONST, 3u, 3000), 1388 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1389 DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u), 1390 DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u), 1391 DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u), 1392 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u), 1393 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1394 DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u), 1395 DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u), 1396 DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u), 1397 DEF_CONST(3, Instruction::CONST, 13u, 4000), 1398 }; 1399 1400 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 7, 7, 4, 7 }; 1401 PrepareSRegToVRegMap(sreg_to_vreg_map); 1402 1403 PrepareIFields(ifields); 1404 PrepareMIRs(mirs); 1405 PerformGVN_DCE(); 1406 1407 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1408 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 13 }; 1409 ExpectValueNamesNE(diff_indexes); 1410 EXPECT_EQ(value_names_[4], value_names_[9]); 1411 EXPECT_EQ(value_names_[5], value_names_[10]); 1412 EXPECT_EQ(value_names_[6], value_names_[11]); 1413 EXPECT_EQ(value_names_[7], value_names_[12]); 1414 1415 const size_t no_null_ck_indexes[] = { 4, 9 }; 1416 ExpectNoNullCheck(no_null_ck_indexes); 1417 1418 static const bool eliminated[] = { 1419 false, false, false, false, false, false, false, false, false, true, true, true, true, false 1420 }; 1421 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1422 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1423 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1424 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1425 } 1426 // Check that the sregs have been renamed correctly. 1427 ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs); 1428 EXPECT_EQ(12, mirs_[7].ssa_rep->defs[0]); // 7 -> 12 1429 ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses); 1430 EXPECT_EQ(6, mirs_[7].ssa_rep->uses[0]); 1431 EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]); 1432 ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs); 1433 EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]); 1434 ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses); 1435 EXPECT_EQ(12, mirs_[8].ssa_rep->uses[0]); // 7 -> 12 1436 } 1437 1438 TEST_F(GvnDeadCodeEliminationTestSimple, KillChain3) { 1439 static const IFieldDef ifields[] = { 1440 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1441 }; 1442 static const MIRDef mirs[] = { 1443 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1444 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1445 DEF_CONST(3, Instruction::CONST, 2u, 2000), 1446 DEF_CONST(3, Instruction::CONST, 3u, 3000), 1447 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1448 DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u), 1449 DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u), 1450 DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u), 1451 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u), 1452 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1453 DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u), 1454 DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u), 1455 DEF_CONST(3, Instruction::CONST, 12u, 4000), 1456 DEF_BINOP(3, Instruction::SUB_INT, 13u, 11u, 3u), 1457 }; 1458 1459 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 7, 4, 7, 4 }; 1460 PrepareSRegToVRegMap(sreg_to_vreg_map); 1461 1462 PrepareIFields(ifields); 1463 PrepareMIRs(mirs); 1464 PerformGVN_DCE(); 1465 1466 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1467 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8, 12 }; 1468 ExpectValueNamesNE(diff_indexes); 1469 EXPECT_EQ(value_names_[4], value_names_[9]); 1470 EXPECT_EQ(value_names_[5], value_names_[10]); 1471 EXPECT_EQ(value_names_[6], value_names_[11]); 1472 EXPECT_EQ(value_names_[7], value_names_[13]); 1473 1474 const size_t no_null_ck_indexes[] = { 4, 9 }; 1475 ExpectNoNullCheck(no_null_ck_indexes); 1476 1477 static const bool eliminated[] = { 1478 false, false, false, false, false, false, false, false, false, true, true, true, false, true 1479 }; 1480 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1481 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1482 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1483 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1484 } 1485 // Check that the sregs have been renamed correctly. 1486 ASSERT_EQ(1, mirs_[7].ssa_rep->num_defs); 1487 EXPECT_EQ(13, mirs_[7].ssa_rep->defs[0]); // 7 -> 13 1488 ASSERT_EQ(2, mirs_[7].ssa_rep->num_uses); 1489 EXPECT_EQ(6, mirs_[7].ssa_rep->uses[0]); 1490 EXPECT_EQ(3, mirs_[7].ssa_rep->uses[1]); 1491 ASSERT_EQ(1, mirs_[8].ssa_rep->num_defs); 1492 EXPECT_EQ(8, mirs_[8].ssa_rep->defs[0]); 1493 ASSERT_EQ(1, mirs_[8].ssa_rep->num_uses); 1494 EXPECT_EQ(13, mirs_[8].ssa_rep->uses[0]); // 7 -> 13 1495 } 1496 1497 TEST_F(GvnDeadCodeEliminationTestSimple, KeepChain1) { 1498 // KillChain2 without the final CONST. 1499 static const IFieldDef ifields[] = { 1500 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1501 }; 1502 static const MIRDef mirs[] = { 1503 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1504 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1505 DEF_CONST(3, Instruction::CONST, 2u, 2000), 1506 DEF_CONST(3, Instruction::CONST, 3u, 3000), 1507 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1508 DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u), 1509 DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u), 1510 DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u), 1511 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u), 1512 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1513 DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u), 1514 DEF_BINOP(3, Instruction::MUL_INT, 11u, 10u, 2u), 1515 DEF_BINOP(3, Instruction::SUB_INT, 12u, 11u, 3u), 1516 }; 1517 1518 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 5, 4, 6, 4, 7, 7, 4 }; 1519 PrepareSRegToVRegMap(sreg_to_vreg_map); 1520 1521 PrepareIFields(ifields); 1522 PrepareMIRs(mirs); 1523 PerformGVN_DCE(); 1524 1525 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1526 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; 1527 ExpectValueNamesNE(diff_indexes); 1528 EXPECT_EQ(value_names_[4], value_names_[9]); 1529 EXPECT_EQ(value_names_[5], value_names_[10]); 1530 EXPECT_EQ(value_names_[6], value_names_[11]); 1531 EXPECT_EQ(value_names_[7], value_names_[12]); 1532 1533 const size_t no_null_ck_indexes[] = { 4, 9 }; 1534 ExpectNoNullCheck(no_null_ck_indexes); 1535 1536 static const bool eliminated[] = { 1537 false, false, false, false, false, false, false, false, false, false, false, false, false 1538 }; 1539 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1540 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1541 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1542 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1543 } 1544 } 1545 1546 TEST_F(GvnDeadCodeEliminationTestSimple, KeepChain2) { 1547 // KillChain1 with MIRs in the middle of the chain. 1548 static const IFieldDef ifields[] = { 1549 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1550 }; 1551 static const MIRDef mirs[] = { 1552 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1553 DEF_CONST(3, Instruction::CONST, 1u, 1000), 1554 DEF_CONST(3, Instruction::CONST, 2u, 2000), 1555 DEF_CONST(3, Instruction::CONST, 3u, 3000), 1556 DEF_IGET(3, Instruction::IGET, 4u, 0u, 0u), 1557 DEF_BINOP(3, Instruction::ADD_INT, 5u, 4u, 1u), 1558 DEF_BINOP(3, Instruction::MUL_INT, 6u, 5u, 2u), 1559 DEF_BINOP(3, Instruction::SUB_INT, 7u, 6u, 3u), 1560 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 8u, 7u), 1561 DEF_IGET(3, Instruction::IGET, 9u, 0u, 0u), 1562 DEF_BINOP(3, Instruction::ADD_INT, 10u, 9u, 1u), 1563 DEF_CONST(3, Instruction::CONST, 11u, 4000), 1564 DEF_UNOP(3, Instruction::INT_TO_FLOAT, 12u, 11u), 1565 DEF_BINOP(3, Instruction::MUL_INT, 13u, 10u, 2u), 1566 DEF_BINOP(3, Instruction::SUB_INT, 14u, 13u, 3u), 1567 }; 1568 1569 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 4, 5, 6, 4, 5, 4, 7, 4, 5 }; 1570 PrepareSRegToVRegMap(sreg_to_vreg_map); 1571 1572 PrepareIFields(ifields); 1573 PrepareMIRs(mirs); 1574 PerformGVN_DCE(); 1575 1576 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1577 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 5, 6, 7, 8 }; 1578 ExpectValueNamesNE(diff_indexes); 1579 EXPECT_EQ(value_names_[4], value_names_[9]); 1580 EXPECT_EQ(value_names_[5], value_names_[10]); 1581 EXPECT_EQ(value_names_[6], value_names_[13]); 1582 EXPECT_EQ(value_names_[7], value_names_[14]); 1583 1584 const size_t no_null_ck_indexes[] = { 4, 9 }; 1585 ExpectNoNullCheck(no_null_ck_indexes); 1586 1587 static const bool eliminated[] = { 1588 false, false, false, false, false, false, false, false, false, 1589 false, false, false, false, false, false 1590 }; 1591 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1592 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1593 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1594 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1595 } 1596 } 1597 1598 TEST_F(GvnDeadCodeEliminationTestDiamond, CreatePhi1) { 1599 static const MIRDef mirs[] = { 1600 DEF_CONST(3, Instruction::CONST, 0u, 1000), 1601 DEF_CONST(4, Instruction::CONST, 1u, 1000), 1602 }; 1603 1604 static const int32_t sreg_to_vreg_map[] = { 0, 0 }; 1605 PrepareSRegToVRegMap(sreg_to_vreg_map); 1606 1607 PrepareMIRs(mirs); 1608 PerformGVN_DCE(); 1609 1610 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1611 EXPECT_EQ(value_names_[0], value_names_[1]); 1612 1613 static const bool eliminated[] = { 1614 false, true, 1615 }; 1616 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1617 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1618 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1619 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1620 } 1621 // Check that we've created a single-input Phi to replace the CONST 3u. 1622 BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4); 1623 MIR* phi = bb4->first_mir_insn; 1624 ASSERT_TRUE(phi != nullptr); 1625 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode)); 1626 ASSERT_EQ(1, phi->ssa_rep->num_uses); 1627 EXPECT_EQ(0, phi->ssa_rep->uses[0]); 1628 ASSERT_EQ(1, phi->ssa_rep->num_defs); 1629 EXPECT_EQ(1, phi->ssa_rep->defs[0]); 1630 EXPECT_EQ(0u, phi->dalvikInsn.vA); 1631 } 1632 1633 TEST_F(GvnDeadCodeEliminationTestDiamond, CreatePhi2) { 1634 static const MIRDef mirs[] = { 1635 DEF_CONST(3, Instruction::CONST, 0u, 1000), 1636 DEF_MOVE(4, Instruction::MOVE, 1u, 0u), 1637 DEF_CONST(4, Instruction::CONST, 2u, 1000), 1638 }; 1639 1640 static const int32_t sreg_to_vreg_map[] = { 0, 1, 0 }; 1641 PrepareSRegToVRegMap(sreg_to_vreg_map); 1642 1643 PrepareMIRs(mirs); 1644 PerformGVN_DCE(); 1645 1646 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1647 EXPECT_EQ(value_names_[0], value_names_[1]); 1648 EXPECT_EQ(value_names_[0], value_names_[2]); 1649 1650 static const bool eliminated[] = { 1651 false, false, true, 1652 }; 1653 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1654 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1655 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1656 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1657 } 1658 // Check that we've created a single-input Phi to replace the CONST 3u. 1659 BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4); 1660 MIR* phi = bb4->first_mir_insn; 1661 ASSERT_TRUE(phi != nullptr); 1662 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode)); 1663 ASSERT_EQ(1, phi->ssa_rep->num_uses); 1664 EXPECT_EQ(0, phi->ssa_rep->uses[0]); 1665 ASSERT_EQ(1, phi->ssa_rep->num_defs); 1666 EXPECT_EQ(2, phi->ssa_rep->defs[0]); 1667 EXPECT_EQ(0u, phi->dalvikInsn.vA); 1668 MIR* move = phi->next; 1669 ASSERT_TRUE(move != nullptr); 1670 ASSERT_EQ(Instruction::MOVE, move->dalvikInsn.opcode); 1671 ASSERT_EQ(1, move->ssa_rep->num_uses); 1672 EXPECT_EQ(2, move->ssa_rep->uses[0]); 1673 ASSERT_EQ(1, move->ssa_rep->num_defs); 1674 EXPECT_EQ(1, move->ssa_rep->defs[0]); 1675 EXPECT_EQ(1u, move->dalvikInsn.vA); 1676 EXPECT_EQ(0u, move->dalvikInsn.vB); 1677 } 1678 1679 TEST_F(GvnDeadCodeEliminationTestDiamond, CreatePhi3) { 1680 static const IFieldDef ifields[] = { 1681 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1682 }; 1683 static const MIRDef mirs[] = { 1684 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1685 DEF_CONST(4, Instruction::CONST, 1u, 1000), 1686 DEF_IPUT(4, Instruction::IPUT, 1u, 0u, 0u), 1687 DEF_CONST(5, Instruction::CONST, 3u, 2000), 1688 DEF_IPUT(5, Instruction::IPUT, 3u, 0u, 0u), 1689 DEF_IGET(6, Instruction::IGET, 5u, 0u, 0u), 1690 }; 1691 1692 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2 /* dummy */, 1, 2 /* dummy */, 1 }; 1693 PrepareSRegToVRegMap(sreg_to_vreg_map); 1694 1695 PrepareIFields(ifields); 1696 PrepareMIRs(mirs); 1697 PerformGVN_DCE(); 1698 1699 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1700 static const size_t diff_indexes[] = { 0, 1, 3, 5 }; 1701 ExpectValueNamesNE(diff_indexes); 1702 1703 const size_t no_null_ck_indexes[] = { 2, 4, 5 }; 1704 ExpectNoNullCheck(no_null_ck_indexes); 1705 1706 static const bool eliminated[] = { 1707 false, false, false, false, false, true, 1708 }; 1709 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1710 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1711 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1712 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1713 } 1714 // Check that we've created a two-input Phi to replace the IGET 5u. 1715 BasicBlock* bb6 = cu_.mir_graph->GetBasicBlock(6); 1716 MIR* phi = bb6->first_mir_insn; 1717 ASSERT_TRUE(phi != nullptr); 1718 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode)); 1719 ASSERT_EQ(2, phi->ssa_rep->num_uses); 1720 EXPECT_EQ(1, phi->ssa_rep->uses[0]); 1721 EXPECT_EQ(3, phi->ssa_rep->uses[1]); 1722 ASSERT_EQ(1, phi->ssa_rep->num_defs); 1723 EXPECT_EQ(5, phi->ssa_rep->defs[0]); 1724 EXPECT_EQ(1u, phi->dalvikInsn.vA); 1725 } 1726 1727 TEST_F(GvnDeadCodeEliminationTestDiamond, KillChainInAnotherBlock1) { 1728 static const IFieldDef ifields[] = { 1729 { 0u, 1u, 0u, false, kDexMemAccessObject }, // linked list 1730 }; 1731 static const MIRDef mirs[] = { 1732 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1733 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 0u, 0u), 1734 DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 1u, 0u), 1735 DEF_IGET(3, Instruction::IGET_OBJECT, 3u, 2u, 0u), 1736 DEF_IGET(3, Instruction::IGET_OBJECT, 4u, 3u, 0u), 1737 DEF_IFZ(3, Instruction::IF_NEZ, 4u), 1738 DEF_IGET(4, Instruction::IGET_OBJECT, 6u, 0u, 0u), 1739 DEF_IGET(4, Instruction::IGET_OBJECT, 7u, 6u, 0u), 1740 DEF_IGET(4, Instruction::IGET_OBJECT, 8u, 7u, 0u), 1741 DEF_IGET(4, Instruction::IGET_OBJECT, 9u, 8u, 0u), 1742 }; 1743 1744 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 2, 3 /* dummy */, 1, 2, 1, 2 }; 1745 PrepareSRegToVRegMap(sreg_to_vreg_map); 1746 1747 PrepareIFields(ifields); 1748 PrepareMIRs(mirs); 1749 PerformGVN_DCE(); 1750 1751 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1752 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4 }; 1753 ExpectValueNamesNE(diff_indexes); 1754 EXPECT_EQ(value_names_[1], value_names_[6]); 1755 EXPECT_EQ(value_names_[2], value_names_[7]); 1756 EXPECT_EQ(value_names_[3], value_names_[8]); 1757 EXPECT_EQ(value_names_[4], value_names_[9]); 1758 1759 const size_t no_null_ck_indexes[] = { 1, 6, 7, 8, 9 }; 1760 ExpectNoNullCheck(no_null_ck_indexes); 1761 1762 static const bool eliminated[] = { 1763 false, false, false, false, false, false, true, true, true, true, 1764 }; 1765 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1766 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1767 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1768 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1769 } 1770 // Check that we've created two single-input Phis to replace the IGET 8u and IGET 9u; 1771 // the IGET 6u and IGET 7u were killed without a replacement. 1772 BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4); 1773 MIR* phi1 = bb4->first_mir_insn; 1774 ASSERT_TRUE(phi1 != nullptr); 1775 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi1->dalvikInsn.opcode)); 1776 MIR* phi2 = phi1->next; 1777 ASSERT_TRUE(phi2 != nullptr); 1778 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi2->dalvikInsn.opcode)); 1779 ASSERT_TRUE(phi2->next == &mirs_[6]); 1780 if (phi1->dalvikInsn.vA == 2u) { 1781 std::swap(phi1, phi2); 1782 } 1783 ASSERT_EQ(1, phi1->ssa_rep->num_uses); 1784 EXPECT_EQ(3, phi1->ssa_rep->uses[0]); 1785 ASSERT_EQ(1, phi1->ssa_rep->num_defs); 1786 EXPECT_EQ(8, phi1->ssa_rep->defs[0]); 1787 EXPECT_EQ(1u, phi1->dalvikInsn.vA); 1788 ASSERT_EQ(1, phi2->ssa_rep->num_uses); 1789 EXPECT_EQ(4, phi2->ssa_rep->uses[0]); 1790 ASSERT_EQ(1, phi2->ssa_rep->num_defs); 1791 EXPECT_EQ(9, phi2->ssa_rep->defs[0]); 1792 EXPECT_EQ(2u, phi2->dalvikInsn.vA); 1793 } 1794 1795 TEST_F(GvnDeadCodeEliminationTestDiamond, KillChainInAnotherBlock2) { 1796 static const IFieldDef ifields[] = { 1797 { 0u, 1u, 0u, false, kDexMemAccessObject }, // linked list 1798 }; 1799 static const MIRDef mirs[] = { 1800 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1801 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 0u, 0u), 1802 DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 1u, 0u), 1803 DEF_IGET(3, Instruction::IGET_OBJECT, 3u, 2u, 0u), 1804 DEF_IGET(3, Instruction::IGET_OBJECT, 4u, 3u, 0u), 1805 DEF_IFZ(3, Instruction::IF_NEZ, 4u), 1806 DEF_IGET(4, Instruction::IGET_OBJECT, 6u, 0u, 0u), 1807 DEF_IGET(4, Instruction::IGET_OBJECT, 7u, 6u, 0u), 1808 DEF_IGET(4, Instruction::IGET_OBJECT, 8u, 7u, 0u), 1809 DEF_CONST(4, Instruction::CONST, 9u, 1000), 1810 }; 1811 1812 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 1, 2, 3 /* dummy */, 1, 2, 1, 2 }; 1813 PrepareSRegToVRegMap(sreg_to_vreg_map); 1814 1815 PrepareIFields(ifields); 1816 PrepareMIRs(mirs); 1817 PerformGVN_DCE(); 1818 1819 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1820 static const size_t diff_indexes[] = { 0, 1, 2, 3, 4, 9 }; 1821 ExpectValueNamesNE(diff_indexes); 1822 EXPECT_EQ(value_names_[1], value_names_[6]); 1823 EXPECT_EQ(value_names_[2], value_names_[7]); 1824 EXPECT_EQ(value_names_[3], value_names_[8]); 1825 1826 const size_t no_null_ck_indexes[] = { 1, 6, 7, 8 }; 1827 ExpectNoNullCheck(no_null_ck_indexes); 1828 1829 static const bool eliminated[] = { 1830 false, false, false, false, false, false, true, true, true, false, 1831 }; 1832 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1833 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1834 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1835 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1836 } 1837 // Check that we've created a single-input Phi to replace the IGET 8u; 1838 // the IGET 6u and IGET 7u were killed without a replacement. 1839 BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4); 1840 MIR* phi = bb4->first_mir_insn; 1841 ASSERT_TRUE(phi != nullptr); 1842 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode)); 1843 ASSERT_TRUE(phi->next == &mirs_[6]); 1844 ASSERT_EQ(1, phi->ssa_rep->num_uses); 1845 EXPECT_EQ(3, phi->ssa_rep->uses[0]); 1846 ASSERT_EQ(1, phi->ssa_rep->num_defs); 1847 EXPECT_EQ(8, phi->ssa_rep->defs[0]); 1848 EXPECT_EQ(1u, phi->dalvikInsn.vA); 1849 } 1850 1851 TEST_F(GvnDeadCodeEliminationTestLoop, IFieldLoopVariable) { 1852 static const IFieldDef ifields[] = { 1853 { 0u, 1u, 0u, false, kDexMemAccessWord }, 1854 }; 1855 static const MIRDef mirs[] = { 1856 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 0u), 1857 DEF_CONST(3, Instruction::CONST, 1u, 1), 1858 DEF_CONST(3, Instruction::CONST, 2u, 0), 1859 DEF_IPUT(3, Instruction::IPUT, 2u, 0u, 0u), 1860 DEF_IGET(4, Instruction::IGET, 4u, 0u, 0u), 1861 DEF_BINOP(4, Instruction::ADD_INT, 5u, 4u, 1u), 1862 DEF_IPUT(4, Instruction::IPUT, 5u, 0u, 0u), 1863 }; 1864 1865 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3 /* dummy */, 2, 2 }; 1866 PrepareSRegToVRegMap(sreg_to_vreg_map); 1867 1868 PrepareIFields(ifields); 1869 PrepareMIRs(mirs); 1870 PerformGVN_DCE(); 1871 1872 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1873 static const size_t diff_indexes[] = { 0, 1, 2, 4, 5 }; 1874 ExpectValueNamesNE(diff_indexes); 1875 1876 const size_t no_null_ck_indexes[] = { 3, 4, 6 }; 1877 ExpectNoNullCheck(no_null_ck_indexes); 1878 1879 static const bool eliminated[] = { 1880 false, false, false, false, true, false, false, 1881 }; 1882 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1883 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1884 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1885 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1886 } 1887 // Check that we've created a two-input Phi to replace the IGET 3u. 1888 BasicBlock* bb4 = cu_.mir_graph->GetBasicBlock(4); 1889 MIR* phi = bb4->first_mir_insn; 1890 ASSERT_TRUE(phi != nullptr); 1891 ASSERT_EQ(kMirOpPhi, static_cast<int>(phi->dalvikInsn.opcode)); 1892 ASSERT_TRUE(phi->next == &mirs_[4]); 1893 ASSERT_EQ(2, phi->ssa_rep->num_uses); 1894 EXPECT_EQ(2, phi->ssa_rep->uses[0]); 1895 EXPECT_EQ(5, phi->ssa_rep->uses[1]); 1896 ASSERT_EQ(1, phi->ssa_rep->num_defs); 1897 EXPECT_EQ(4, phi->ssa_rep->defs[0]); 1898 EXPECT_EQ(2u, phi->dalvikInsn.vA); 1899 } 1900 1901 TEST_F(GvnDeadCodeEliminationTestDiamond, LongOverlaps1) { 1902 static const MIRDef mirs[] = { 1903 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u), 1904 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 2u, 1000u), 1905 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 4u, 0u), 1906 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 6u, 2u), 1907 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 8u, 4u), 1908 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 10u, 6u), 1909 }; 1910 1911 // The last insn should overlap the first and second. 1912 static const int32_t sreg_to_vreg_map[] = { 1, 2, 3, 4, 5, 6, 7, 8, 0, 1, 2, 3 }; 1913 PrepareSRegToVRegMap(sreg_to_vreg_map); 1914 1915 PrepareMIRs(mirs); 1916 static const int32_t wide_sregs[] = { 0, 2, 4, 6, 8, 10 }; 1917 MarkAsWideSRegs(wide_sregs); 1918 PerformGVN_DCE(); 1919 1920 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1921 EXPECT_EQ(value_names_[0], value_names_[1]); 1922 EXPECT_EQ(value_names_[0], value_names_[2]); 1923 EXPECT_EQ(value_names_[0], value_names_[3]); 1924 EXPECT_EQ(value_names_[0], value_names_[4]); 1925 1926 static const bool eliminated[] = { 1927 false, false, false, false, false, false, 1928 }; 1929 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1930 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1931 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1932 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1933 } 1934 } 1935 1936 TEST_F(GvnDeadCodeEliminationTestSimple, LongOverlaps2) { 1937 static const MIRDef mirs[] = { 1938 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u), 1939 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 2u, 0u), 1940 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 4u, 2u), 1941 }; 1942 1943 // The last insn should overlap the first and second. 1944 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 1, 2 }; 1945 PrepareSRegToVRegMap(sreg_to_vreg_map); 1946 1947 PrepareMIRs(mirs); 1948 static const int32_t wide_sregs[] = { 0, 2, 4 }; 1949 MarkAsWideSRegs(wide_sregs); 1950 PerformGVN_DCE(); 1951 1952 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1953 EXPECT_EQ(value_names_[0], value_names_[1]); 1954 EXPECT_EQ(value_names_[0], value_names_[2]); 1955 1956 static const bool eliminated[] = { 1957 false, true, true, 1958 }; 1959 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1960 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1961 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1962 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1963 } 1964 // Check that the CONST_WIDE registers have been correctly renamed. 1965 MIR* const_wide = &mirs_[0]; 1966 ASSERT_EQ(2u, const_wide->ssa_rep->num_defs); 1967 EXPECT_EQ(4, const_wide->ssa_rep->defs[0]); 1968 EXPECT_EQ(5, const_wide->ssa_rep->defs[1]); 1969 EXPECT_EQ(1u, const_wide->dalvikInsn.vA); 1970 } 1971 1972 TEST_F(GvnDeadCodeEliminationTestSimple, LongOverlaps3) { 1973 static const MIRDef mirs[] = { 1974 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000u), 1975 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 2u, 0u), 1976 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 4u, 2u), 1977 }; 1978 1979 // The last insn should overlap the first and second. 1980 static const int32_t sreg_to_vreg_map[] = { 2, 3, 0, 1, 1, 2 }; 1981 PrepareSRegToVRegMap(sreg_to_vreg_map); 1982 1983 PrepareMIRs(mirs); 1984 static const int32_t wide_sregs[] = { 0, 2, 4 }; 1985 MarkAsWideSRegs(wide_sregs); 1986 PerformGVN_DCE(); 1987 1988 ASSERT_EQ(arraysize(mirs), value_names_.size()); 1989 EXPECT_EQ(value_names_[0], value_names_[1]); 1990 EXPECT_EQ(value_names_[0], value_names_[2]); 1991 1992 static const bool eliminated[] = { 1993 false, true, true, 1994 }; 1995 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 1996 for (size_t i = 0; i != arraysize(eliminated); ++i) { 1997 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 1998 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 1999 } 2000 // Check that the CONST_WIDE registers have been correctly renamed. 2001 MIR* const_wide = &mirs_[0]; 2002 ASSERT_EQ(2u, const_wide->ssa_rep->num_defs); 2003 EXPECT_EQ(4, const_wide->ssa_rep->defs[0]); 2004 EXPECT_EQ(5, const_wide->ssa_rep->defs[1]); 2005 EXPECT_EQ(1u, const_wide->dalvikInsn.vA); 2006 } 2007 2008 TEST_F(GvnDeadCodeEliminationTestSimple, MixedOverlaps1) { 2009 static const MIRDef mirs[] = { 2010 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 2011 DEF_MOVE(3, Instruction::MOVE, 1u, 0u), 2012 DEF_CONST(3, Instruction::CONST, 2u, 2000u), 2013 { 3, Instruction::INT_TO_LONG, 0, 0u, 1, { 2u }, 2, { 3u, 4u } }, 2014 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 5u, 3u), 2015 DEF_CONST(3, Instruction::CONST, 7u, 3000u), 2016 DEF_CONST(3, Instruction::CONST, 8u, 4000u), 2017 }; 2018 2019 static const int32_t sreg_to_vreg_map[] = { 1, 2, 0, 0, 1, 3, 4, 0, 1 }; 2020 PrepareSRegToVRegMap(sreg_to_vreg_map); 2021 2022 PrepareMIRs(mirs); 2023 static const int32_t wide_sregs[] = { 3, 5 }; 2024 MarkAsWideSRegs(wide_sregs); 2025 PerformGVN_DCE(); 2026 2027 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2028 static const size_t diff_indexes[] = { 0, 2, 3, 5, 6 }; 2029 ExpectValueNamesNE(diff_indexes); 2030 EXPECT_EQ(value_names_[0], value_names_[1]); 2031 EXPECT_EQ(value_names_[3], value_names_[4]); 2032 2033 static const bool eliminated[] = { 2034 false, true, false, false, true, false, false, 2035 }; 2036 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 2037 for (size_t i = 0; i != arraysize(eliminated); ++i) { 2038 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 2039 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 2040 } 2041 // Check renamed registers in CONST. 2042 MIR* cst = &mirs_[0]; 2043 ASSERT_EQ(Instruction::CONST, cst->dalvikInsn.opcode); 2044 ASSERT_EQ(0, cst->ssa_rep->num_uses); 2045 ASSERT_EQ(1, cst->ssa_rep->num_defs); 2046 EXPECT_EQ(1, cst->ssa_rep->defs[0]); 2047 EXPECT_EQ(2u, cst->dalvikInsn.vA); 2048 // Check renamed registers in INT_TO_LONG. 2049 MIR* int_to_long = &mirs_[3]; 2050 ASSERT_EQ(Instruction::INT_TO_LONG, int_to_long->dalvikInsn.opcode); 2051 ASSERT_EQ(1, int_to_long->ssa_rep->num_uses); 2052 EXPECT_EQ(2, int_to_long->ssa_rep->uses[0]); 2053 ASSERT_EQ(2, int_to_long->ssa_rep->num_defs); 2054 EXPECT_EQ(5, int_to_long->ssa_rep->defs[0]); 2055 EXPECT_EQ(6, int_to_long->ssa_rep->defs[1]); 2056 EXPECT_EQ(3u, int_to_long->dalvikInsn.vA); 2057 EXPECT_EQ(0u, int_to_long->dalvikInsn.vB); 2058 } 2059 2060 TEST_F(GvnDeadCodeEliminationTestSimple, UnusedRegs1) { 2061 static const MIRDef mirs[] = { 2062 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 2063 DEF_CONST(3, Instruction::CONST, 1u, 2000u), 2064 DEF_BINOP(3, Instruction::ADD_INT, 2u, 1u, 0u), 2065 DEF_CONST(3, Instruction::CONST, 3u, 1000u), // NOT killed (b/21702651). 2066 DEF_BINOP(3, Instruction::ADD_INT, 4u, 1u, 3u), // Killed (RecordPass) 2067 DEF_CONST(3, Instruction::CONST, 5u, 2000u), // Killed with 9u (BackwardPass) 2068 DEF_BINOP(3, Instruction::ADD_INT, 6u, 5u, 0u), // Killed (RecordPass) 2069 DEF_CONST(3, Instruction::CONST, 7u, 4000u), 2070 DEF_MOVE(3, Instruction::MOVE, 8u, 0u), // Killed with 6u (BackwardPass) 2071 }; 2072 2073 static const int32_t sreg_to_vreg_map[] = { 1, 2, 3, 0, 3, 0, 3, 4, 0 }; 2074 PrepareSRegToVRegMap(sreg_to_vreg_map); 2075 2076 PrepareMIRs(mirs); 2077 PerformGVN_DCE(); 2078 2079 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2080 static const size_t diff_indexes[] = { 0, 1, 2, 7 }; 2081 ExpectValueNamesNE(diff_indexes); 2082 EXPECT_EQ(value_names_[0], value_names_[3]); 2083 EXPECT_EQ(value_names_[2], value_names_[4]); 2084 EXPECT_EQ(value_names_[1], value_names_[5]); 2085 EXPECT_EQ(value_names_[2], value_names_[6]); 2086 EXPECT_EQ(value_names_[0], value_names_[8]); 2087 2088 static const bool eliminated[] = { 2089 false, false, false, false, true, true, true, false, true, 2090 }; 2091 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 2092 for (size_t i = 0; i != arraysize(eliminated); ++i) { 2093 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 2094 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 2095 } 2096 } 2097 2098 TEST_F(GvnDeadCodeEliminationTestSimple, UnusedRegs2) { 2099 static const MIRDef mirs[] = { 2100 DEF_CONST(3, Instruction::CONST, 0u, 1000u), 2101 DEF_CONST(3, Instruction::CONST, 1u, 2000u), 2102 DEF_BINOP(3, Instruction::ADD_INT, 2u, 1u, 0u), 2103 DEF_CONST(3, Instruction::CONST, 3u, 1000u), // Killed (BackwardPass; b/21702651) 2104 DEF_BINOP(3, Instruction::ADD_INT, 4u, 1u, 3u), // Killed (RecordPass) 2105 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 5u, 4000u), 2106 { 3, Instruction::LONG_TO_INT, 0, 0u, 2, { 5u, 6u }, 1, { 7u } }, 2107 DEF_BINOP(3, Instruction::ADD_INT, 8u, 7u, 0u), 2108 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 9u, 4000u), // Killed with 12u (BackwardPass) 2109 DEF_CONST(3, Instruction::CONST, 11u, 6000u), 2110 { 3, Instruction::LONG_TO_INT, 0, 0u, 2, { 9u, 10u }, 1, { 12u } }, // Killed with 9u (BP) 2111 }; 2112 2113 static const int32_t sreg_to_vreg_map[] = { 2114 2, 3, 4, 1, 4, 5, 6 /* high word */, 0, 7, 0, 1 /* high word */, 8, 0 2115 }; 2116 PrepareSRegToVRegMap(sreg_to_vreg_map); 2117 2118 PrepareMIRs(mirs); 2119 static const int32_t wide_sregs[] = { 5, 9 }; 2120 MarkAsWideSRegs(wide_sregs); 2121 PerformGVN_DCE(); 2122 2123 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2124 static const size_t diff_indexes[] = { 0, 1, 2, 5, 6, 7, 9 }; 2125 ExpectValueNamesNE(diff_indexes); 2126 EXPECT_EQ(value_names_[0], value_names_[3]); 2127 EXPECT_EQ(value_names_[2], value_names_[4]); 2128 EXPECT_EQ(value_names_[5], value_names_[8]); 2129 EXPECT_EQ(value_names_[6], value_names_[10]); 2130 2131 static const bool eliminated[] = { 2132 false, false, false, true, true, false, false, false, true, false, true, 2133 }; 2134 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 2135 for (size_t i = 0; i != arraysize(eliminated); ++i) { 2136 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 2137 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 2138 } 2139 } 2140 2141 TEST_F(GvnDeadCodeEliminationTestSimple, ArrayLengthThrows) { 2142 static const MIRDef mirs[] = { 2143 DEF_CONST(3, Instruction::CONST, 0u, 0), // null 2144 DEF_UNOP(3, Instruction::ARRAY_LENGTH, 1u, 0u), // null.length 2145 DEF_CONST(3, Instruction::CONST, 2u, 1000u), // Overwrite the array-length dest. 2146 }; 2147 2148 static const int32_t sreg_to_vreg_map[] = { 0, 1, 1 }; 2149 PrepareSRegToVRegMap(sreg_to_vreg_map); 2150 2151 PrepareMIRs(mirs); 2152 PerformGVN_DCE(); 2153 2154 ASSERT_EQ(arraysize(mirs), value_names_.size()); 2155 static const size_t diff_indexes[] = { 0, 1, 2 }; 2156 ExpectValueNamesNE(diff_indexes); 2157 2158 static const bool eliminated[] = { 2159 false, false, false, 2160 }; 2161 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 2162 for (size_t i = 0; i != arraysize(eliminated); ++i) { 2163 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 2164 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 2165 } 2166 } 2167 2168 TEST_F(GvnDeadCodeEliminationTestSimple, Dependancy) { 2169 static const MIRDef mirs[] = { 2170 DEF_MOVE(3, Instruction::MOVE, 5u, 1u), // move v5,v1 2171 DEF_MOVE(3, Instruction::MOVE, 6u, 1u), // move v12,v1 2172 DEF_MOVE(3, Instruction::MOVE, 7u, 0u), // move v13,v0 2173 DEF_MOVE_WIDE(3, Instruction::MOVE_WIDE, 8u, 2u), // move v0_1,v2_3 2174 DEF_MOVE(3, Instruction::MOVE, 10u, 6u), // move v3,v12 2175 DEF_MOVE(3, Instruction::MOVE, 11u, 4u), // move v2,v4 2176 DEF_MOVE(3, Instruction::MOVE, 12u, 7u), // move v4,v13 2177 DEF_MOVE(3, Instruction::MOVE, 13, 11u), // move v12,v2 2178 DEF_MOVE(3, Instruction::MOVE, 14u, 10u), // move v2,v3 2179 DEF_MOVE(3, Instruction::MOVE, 15u, 5u), // move v3,v5 2180 DEF_MOVE(3, Instruction::MOVE, 16u, 12u), // move v5,v4 2181 }; 2182 2183 static const int32_t sreg_to_vreg_map[] = { 0, 1, 2, 3, 4, 5, 12, 13, 0, 1, 3, 2, 4, 12, 2, 3, 5 }; 2184 PrepareSRegToVRegMap(sreg_to_vreg_map); 2185 2186 PrepareMIRs(mirs); 2187 static const int32_t wide_sregs[] = { 2, 8 }; 2188 MarkAsWideSRegs(wide_sregs); 2189 PerformGVN_DCE(); 2190 2191 static const bool eliminated[] = { 2192 false, false, false, false, false, false, false, true, true, false, false, 2193 }; 2194 static_assert(arraysize(eliminated) == arraysize(mirs), "array size mismatch"); 2195 for (size_t i = 0; i != arraysize(eliminated); ++i) { 2196 bool actually_eliminated = (static_cast<int>(mirs_[i].dalvikInsn.opcode) == kMirOpNop); 2197 EXPECT_EQ(eliminated[i], actually_eliminated) << i; 2198 } 2199 } 2200 2201 } // namespace art 2202
