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 
DoPrepareIFields(const IFieldDef * defs,size_t count)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>
PrepareIFields(const IFieldDef (& defs)[count])161   void PrepareIFields(const IFieldDef (&defs)[count]) {
162     DoPrepareIFields(defs, count);
163   }
164 
DoPrepareSFields(const SFieldDef * defs,size_t count)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>
PrepareSFields(const SFieldDef (& defs)[count])186   void PrepareSFields(const SFieldDef (&defs)[count]) {
187     DoPrepareSFields(defs, count);
188   }
189 
DoPrepareBasicBlocks(const BBDef * defs,size_t count)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>
PrepareBasicBlocks(const BBDef (& defs)[count])234   void PrepareBasicBlocks(const BBDef (&defs)[count]) {
235     DoPrepareBasicBlocks(defs, count);
236   }
237 
SRegToVReg(int32_t s_reg,bool wide)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 
SRegToVReg(int32_t * uses,size_t * use,bool wide)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 
DoPrepareMIRs(const MIRDef * defs,size_t count)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>
PrepareMIRs(const MIRDef (& defs)[count])329   void PrepareMIRs(const MIRDef (&defs)[count]) {
330     DoPrepareMIRs(defs, count);
331   }
332 
333   template <size_t count>
PrepareSRegToVRegMap(const int (& map)[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 
PerformGVN()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 
PerformGVNCodeModifications()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 
FillVregToSsaRegExitMaps()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>
MarkAsWideSRegs(const int32_t (& sregs)[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 
PerformDCE()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 
PerformGVN_DCE()432   void PerformGVN_DCE() {
433     PerformGVN();
434     PerformGVNCodeModifications();  // Eliminate null/range checks.
435     PerformDCE();
436   }
437 
438   template <size_t count>
ExpectValueNamesNE(const size_t (& indexes)[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>
ExpectNoNullCheck(const size_t (& indexes)[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 
GvnDeadCodeEliminationTest()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 
GvnDeadCodeEliminationTestSimple()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 
GvnDeadCodeEliminationTestDiamond()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 
GvnDeadCodeEliminationTestLoop()576 GvnDeadCodeEliminationTestLoop::GvnDeadCodeEliminationTestLoop()
577     : GvnDeadCodeEliminationTest() {
578   PrepareBasicBlocks(kLoopBbs);
579 }
580 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename2)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename3)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename4)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename5)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename6)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename7)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename8)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Rename9)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 
TEST_F(GvnDeadCodeEliminationTestSimple,NoRename1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,NoRename2)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 
TEST_F(GvnDeadCodeEliminationTestSimple,NoRename3)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 
TEST_F(GvnDeadCodeEliminationTestSimple,NoRename4)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Simple1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Simple2)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Simple3)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Simple4)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 
TEST_F(GvnDeadCodeEliminationTestSimple,KillChain1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,KillChain2)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 
TEST_F(GvnDeadCodeEliminationTestSimple,KillChain3)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 
TEST_F(GvnDeadCodeEliminationTestSimple,KeepChain1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,KeepChain2)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 
TEST_F(GvnDeadCodeEliminationTestDiamond,CreatePhi1)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 
TEST_F(GvnDeadCodeEliminationTestDiamond,CreatePhi2)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 
TEST_F(GvnDeadCodeEliminationTestDiamond,CreatePhi3)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 
TEST_F(GvnDeadCodeEliminationTestDiamond,KillChainInAnotherBlock1)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 
TEST_F(GvnDeadCodeEliminationTestDiamond,KillChainInAnotherBlock2)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 
TEST_F(GvnDeadCodeEliminationTestLoop,IFieldLoopVariable)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 
TEST_F(GvnDeadCodeEliminationTestDiamond,LongOverlaps1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,LongOverlaps2)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 
TEST_F(GvnDeadCodeEliminationTestSimple,LongOverlaps3)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 
TEST_F(GvnDeadCodeEliminationTestSimple,MixedOverlaps1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,UnusedRegs1)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 
TEST_F(GvnDeadCodeEliminationTestSimple,UnusedRegs2)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 
TEST_F(GvnDeadCodeEliminationTestSimple,ArrayLengthThrows)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 
TEST_F(GvnDeadCodeEliminationTestSimple,Dependancy)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