1 /*
2 * Copyright (C) 2014 The Android Open Source Project
3 *
4 * Licensed under the Apache License, Version 2.0 (the "License");
5 * you may not use this file except in compliance with the License.
6 * You may obtain a copy of the License at
7 *
8 * http://www.apache.org/licenses/LICENSE-2.0
9 *
10 * Unless required by applicable law or agreed to in writing, software
11 * distributed under the License is distributed on an "AS IS" BASIS,
12 * WITHOUT WARRANTIES OR CONDITIONS OF ANY KIND, either express or implied.
13 * See the License for the specific language governing permissions and
14 * limitations under the License.
15 */
16
17 #include "base/logging.h"
18 #include "dataflow_iterator-inl.h"
19 #include "dex/mir_field_info.h"
20 #include "global_value_numbering.h"
21 #include "local_value_numbering.h"
22 #include "gtest/gtest.h"
23
24 namespace art {
25
26 class GlobalValueNumberingTest : 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_BINOP(bb, opcode, result, src1, src2) \
137 { bb, opcode, 0u, 0u, 2, { src1, src2 }, 1, { result } }
138 #define DEF_UNOP(bb, opcode, result, src) DEF_MOVE(bb, opcode, result, src)
139
DoPrepareIFields(const IFieldDef * defs,size_t count)140 void DoPrepareIFields(const IFieldDef* defs, size_t count) {
141 cu_.mir_graph->ifield_lowering_infos_.clear();
142 cu_.mir_graph->ifield_lowering_infos_.reserve(count);
143 for (size_t i = 0u; i != count; ++i) {
144 const IFieldDef* def = &defs[i];
145 MirIFieldLoweringInfo field_info(def->field_idx, def->type, false);
146 if (def->declaring_dex_file != 0u) {
147 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
148 field_info.declaring_field_idx_ = def->declaring_field_idx;
149 field_info.flags_ &= ~(def->is_volatile ? 0u : MirSFieldLoweringInfo::kFlagIsVolatile);
150 }
151 cu_.mir_graph->ifield_lowering_infos_.push_back(field_info);
152 }
153 }
154
155 template <size_t count>
PrepareIFields(const IFieldDef (& defs)[count])156 void PrepareIFields(const IFieldDef (&defs)[count]) {
157 DoPrepareIFields(defs, count);
158 }
159
DoPrepareSFields(const SFieldDef * defs,size_t count)160 void DoPrepareSFields(const SFieldDef* defs, size_t count) {
161 cu_.mir_graph->sfield_lowering_infos_.clear();
162 cu_.mir_graph->sfield_lowering_infos_.reserve(count);
163 for (size_t i = 0u; i != count; ++i) {
164 const SFieldDef* def = &defs[i];
165 MirSFieldLoweringInfo field_info(def->field_idx, def->type);
166 // Mark even unresolved fields as initialized.
167 field_info.flags_ |= MirSFieldLoweringInfo::kFlagClassIsInitialized;
168 // NOTE: MirSFieldLoweringInfo::kFlagClassIsInDexCache isn't used by GVN.
169 if (def->declaring_dex_file != 0u) {
170 field_info.declaring_dex_file_ = reinterpret_cast<const DexFile*>(def->declaring_dex_file);
171 field_info.declaring_field_idx_ = def->declaring_field_idx;
172 field_info.flags_ &= ~(def->is_volatile ? 0u : MirSFieldLoweringInfo::kFlagIsVolatile);
173 }
174 cu_.mir_graph->sfield_lowering_infos_.push_back(field_info);
175 }
176 }
177
178 template <size_t count>
PrepareSFields(const SFieldDef (& defs)[count])179 void PrepareSFields(const SFieldDef (&defs)[count]) {
180 DoPrepareSFields(defs, count);
181 }
182
DoPrepareBasicBlocks(const BBDef * defs,size_t count)183 void DoPrepareBasicBlocks(const BBDef* defs, size_t count) {
184 cu_.mir_graph->block_id_map_.clear();
185 cu_.mir_graph->block_list_.clear();
186 ASSERT_LT(3u, count); // null, entry, exit and at least one bytecode block.
187 ASSERT_EQ(kNullBlock, defs[0].type);
188 ASSERT_EQ(kEntryBlock, defs[1].type);
189 ASSERT_EQ(kExitBlock, defs[2].type);
190 for (size_t i = 0u; i != count; ++i) {
191 const BBDef* def = &defs[i];
192 BasicBlock* bb = cu_.mir_graph->CreateNewBB(def->type);
193 if (def->num_successors <= 2) {
194 bb->successor_block_list_type = kNotUsed;
195 bb->fall_through = (def->num_successors >= 1) ? def->successors[0] : 0u;
196 bb->taken = (def->num_successors >= 2) ? def->successors[1] : 0u;
197 } else {
198 bb->successor_block_list_type = kPackedSwitch;
199 bb->fall_through = 0u;
200 bb->taken = 0u;
201 bb->successor_blocks.reserve(def->num_successors);
202 for (size_t j = 0u; j != def->num_successors; ++j) {
203 SuccessorBlockInfo* successor_block_info =
204 static_cast<SuccessorBlockInfo*>(cu_.arena.Alloc(sizeof(SuccessorBlockInfo),
205 kArenaAllocSuccessor));
206 successor_block_info->block = j;
207 successor_block_info->key = 0u; // Not used by class init check elimination.
208 bb->successor_blocks.push_back(successor_block_info);
209 }
210 }
211 bb->predecessors.assign(def->predecessors, def->predecessors + def->num_predecessors);
212 if (def->type == kDalvikByteCode || def->type == kEntryBlock || def->type == kExitBlock) {
213 bb->data_flow_info = static_cast<BasicBlockDataFlow*>(
214 cu_.arena.Alloc(sizeof(BasicBlockDataFlow), kArenaAllocDFInfo));
215 bb->data_flow_info->live_in_v = live_in_v_;
216 }
217 }
218 ASSERT_EQ(count, cu_.mir_graph->block_list_.size());
219 cu_.mir_graph->entry_block_ = cu_.mir_graph->block_list_[1];
220 ASSERT_EQ(kEntryBlock, cu_.mir_graph->entry_block_->block_type);
221 cu_.mir_graph->exit_block_ = cu_.mir_graph->block_list_[2];
222 ASSERT_EQ(kExitBlock, cu_.mir_graph->exit_block_->block_type);
223 }
224
225 template <size_t count>
PrepareBasicBlocks(const BBDef (& defs)[count])226 void PrepareBasicBlocks(const BBDef (&defs)[count]) {
227 DoPrepareBasicBlocks(defs, count);
228 }
229
DoPrepareMIRs(const MIRDef * defs,size_t count)230 void DoPrepareMIRs(const MIRDef* defs, size_t count) {
231 mir_count_ = count;
232 mirs_ = cu_.arena.AllocArray<MIR>(count, kArenaAllocMIR);
233 ssa_reps_.resize(count);
234 for (size_t i = 0u; i != count; ++i) {
235 const MIRDef* def = &defs[i];
236 MIR* mir = &mirs_[i];
237 ASSERT_LT(def->bbid, cu_.mir_graph->block_list_.size());
238 BasicBlock* bb = cu_.mir_graph->block_list_[def->bbid];
239 bb->AppendMIR(mir);
240 mir->dalvikInsn.opcode = def->opcode;
241 mir->dalvikInsn.vB = static_cast<int32_t>(def->value);
242 mir->dalvikInsn.vB_wide = def->value;
243 if (IsInstructionIGetOrIPut(def->opcode)) {
244 ASSERT_LT(def->field_info, cu_.mir_graph->ifield_lowering_infos_.size());
245 mir->meta.ifield_lowering_info = def->field_info;
246 ASSERT_EQ(cu_.mir_graph->ifield_lowering_infos_[def->field_info].MemAccessType(),
247 IGetOrIPutMemAccessType(def->opcode));
248 } else if (IsInstructionSGetOrSPut(def->opcode)) {
249 ASSERT_LT(def->field_info, cu_.mir_graph->sfield_lowering_infos_.size());
250 mir->meta.sfield_lowering_info = def->field_info;
251 ASSERT_EQ(cu_.mir_graph->sfield_lowering_infos_[def->field_info].MemAccessType(),
252 SGetOrSPutMemAccessType(def->opcode));
253 } else if (def->opcode == static_cast<Instruction::Code>(kMirOpPhi)) {
254 mir->meta.phi_incoming =
255 allocator_->AllocArray<BasicBlockId>(def->num_uses, kArenaAllocDFInfo);
256 ASSERT_EQ(def->num_uses, bb->predecessors.size());
257 std::copy(bb->predecessors.begin(), bb->predecessors.end(), mir->meta.phi_incoming);
258 }
259 mir->ssa_rep = &ssa_reps_[i];
260 mir->ssa_rep->num_uses = def->num_uses;
261 mir->ssa_rep->uses = const_cast<int32_t*>(def->uses); // Not modified by LVN.
262 mir->ssa_rep->num_defs = def->num_defs;
263 mir->ssa_rep->defs = const_cast<int32_t*>(def->defs); // Not modified by LVN.
264 mir->dalvikInsn.opcode = def->opcode;
265 mir->offset = i; // LVN uses offset only for debug output
266 mir->optimization_flags = 0u;
267 }
268 DexFile::CodeItem* code_item = static_cast<DexFile::CodeItem*>(
269 cu_.arena.Alloc(sizeof(DexFile::CodeItem), kArenaAllocMisc));
270 code_item->insns_size_in_code_units_ = 2u * count;
271 cu_.mir_graph->current_code_item_ = code_item;
272 }
273
274 template <size_t count>
PrepareMIRs(const MIRDef (& defs)[count])275 void PrepareMIRs(const MIRDef (&defs)[count]) {
276 DoPrepareMIRs(defs, count);
277 }
278
DoPrepareVregToSsaMapExit(BasicBlockId bb_id,const int32_t * map,size_t count)279 void DoPrepareVregToSsaMapExit(BasicBlockId bb_id, const int32_t* map, size_t count) {
280 BasicBlock* bb = cu_.mir_graph->GetBasicBlock(bb_id);
281 ASSERT_TRUE(bb != nullptr);
282 ASSERT_TRUE(bb->data_flow_info != nullptr);
283 bb->data_flow_info->vreg_to_ssa_map_exit =
284 cu_.arena.AllocArray<int32_t>(count, kArenaAllocDFInfo);
285 std::copy_n(map, count, bb->data_flow_info->vreg_to_ssa_map_exit);
286 }
287
288 template <size_t count>
PrepareVregToSsaMapExit(BasicBlockId bb_id,const int32_t (& map)[count])289 void PrepareVregToSsaMapExit(BasicBlockId bb_id, const int32_t (&map)[count]) {
290 DoPrepareVregToSsaMapExit(bb_id, map, count);
291 }
292
293 template <size_t count>
MarkAsWideSRegs(const int32_t (& sregs)[count])294 void MarkAsWideSRegs(const int32_t (&sregs)[count]) {
295 for (int32_t sreg : sregs) {
296 cu_.mir_graph->reg_location_[sreg].wide = true;
297 cu_.mir_graph->reg_location_[sreg + 1].wide = true;
298 cu_.mir_graph->reg_location_[sreg + 1].high_word = true;
299 }
300 }
301
PerformGVN()302 void PerformGVN() {
303 DoPerformGVN<LoopRepeatingTopologicalSortIterator>();
304 }
305
PerformPreOrderDfsGVN()306 void PerformPreOrderDfsGVN() {
307 DoPerformGVN<RepeatingPreOrderDfsIterator>();
308 }
309
310 template <typename IteratorType>
DoPerformGVN()311 void DoPerformGVN() {
312 cu_.mir_graph->SSATransformationStart();
313 cu_.mir_graph->ComputeDFSOrders();
314 cu_.mir_graph->ComputeDominators();
315 cu_.mir_graph->ComputeTopologicalSortOrder();
316 cu_.mir_graph->SSATransformationEnd();
317 cu_.mir_graph->temp_.gvn.ifield_ids = GlobalValueNumbering::PrepareGvnFieldIds(
318 allocator_.get(), cu_.mir_graph->ifield_lowering_infos_);
319 cu_.mir_graph->temp_.gvn.sfield_ids = GlobalValueNumbering::PrepareGvnFieldIds(
320 allocator_.get(), cu_.mir_graph->sfield_lowering_infos_);
321 ASSERT_TRUE(gvn_ == nullptr);
322 gvn_.reset(new (allocator_.get()) GlobalValueNumbering(&cu_, allocator_.get(),
323 GlobalValueNumbering::kModeGvn));
324 value_names_.resize(mir_count_, 0xffffu);
325 IteratorType iterator(cu_.mir_graph.get());
326 bool change = false;
327 for (BasicBlock* bb = iterator.Next(change); bb != nullptr; bb = iterator.Next(change)) {
328 LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb);
329 if (lvn != nullptr) {
330 for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
331 value_names_[mir - mirs_] = lvn->GetValueNumber(mir);
332 }
333 }
334 change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb);
335 ASSERT_TRUE(gvn_->Good());
336 }
337 }
338
PerformGVNCodeModifications()339 void PerformGVNCodeModifications() {
340 ASSERT_TRUE(gvn_ != nullptr);
341 ASSERT_TRUE(gvn_->Good());
342 gvn_->StartPostProcessing();
343 TopologicalSortIterator iterator(cu_.mir_graph.get());
344 for (BasicBlock* bb = iterator.Next(); bb != nullptr; bb = iterator.Next()) {
345 LocalValueNumbering* lvn = gvn_->PrepareBasicBlock(bb);
346 if (lvn != nullptr) {
347 for (MIR* mir = bb->first_mir_insn; mir != nullptr; mir = mir->next) {
348 uint16_t value_name = lvn->GetValueNumber(mir);
349 ASSERT_EQ(value_name, value_names_[mir - mirs_]);
350 }
351 }
352 bool change = (lvn != nullptr) && gvn_->FinishBasicBlock(bb);
353 ASSERT_FALSE(change);
354 ASSERT_TRUE(gvn_->Good());
355 }
356 }
357
GlobalValueNumberingTest()358 GlobalValueNumberingTest()
359 : pool_(),
360 cu_(&pool_, kRuntimeISA, nullptr, nullptr),
361 mir_count_(0u),
362 mirs_(nullptr),
363 ssa_reps_(),
364 allocator_(),
365 gvn_(),
366 value_names_(),
367 live_in_v_(new (&cu_.arena) ArenaBitVector(&cu_.arena, kMaxSsaRegs, false, kBitMapMisc)) {
368 cu_.mir_graph.reset(new MIRGraph(&cu_, &cu_.arena));
369 cu_.access_flags = kAccStatic; // Don't let "this" interfere with this test.
370 allocator_.reset(ScopedArenaAllocator::Create(&cu_.arena_stack));
371 // By default, the zero-initialized reg_location_[.] with ref == false tells LVN that
372 // 0 constants are integral, not references, and the values are all narrow.
373 // Nothing else is used by LVN/GVN. Tests can override the default values as needed.
374 cu_.mir_graph->reg_location_ =
375 cu_.arena.AllocArray<RegLocation>(kMaxSsaRegs, kArenaAllocRegAlloc);
376 cu_.mir_graph->num_ssa_regs_ = kMaxSsaRegs;
377 // Bind all possible sregs to live vregs for test purposes.
378 live_in_v_->SetInitialBits(kMaxSsaRegs);
379 cu_.mir_graph->ssa_base_vregs_.reserve(kMaxSsaRegs);
380 cu_.mir_graph->ssa_subscripts_.reserve(kMaxSsaRegs);
381 for (unsigned int i = 0; i < kMaxSsaRegs; i++) {
382 cu_.mir_graph->ssa_base_vregs_.push_back(i);
383 cu_.mir_graph->ssa_subscripts_.push_back(0);
384 }
385 // Set shorty for a void-returning method without arguments.
386 cu_.shorty = "V";
387 }
388
389 static constexpr size_t kMaxSsaRegs = 16384u;
390
391 ArenaPool pool_;
392 CompilationUnit cu_;
393 size_t mir_count_;
394 MIR* mirs_;
395 std::vector<SSARepresentation> ssa_reps_;
396 std::unique_ptr<ScopedArenaAllocator> allocator_;
397 std::unique_ptr<GlobalValueNumbering> gvn_;
398 std::vector<uint16_t> value_names_;
399 ArenaBitVector* live_in_v_;
400 };
401
402 constexpr uint16_t GlobalValueNumberingTest::kNoValue;
403
404 class GlobalValueNumberingTestDiamond : public GlobalValueNumberingTest {
405 public:
406 GlobalValueNumberingTestDiamond();
407
408 private:
409 static const BBDef kDiamondBbs[];
410 };
411
412 const GlobalValueNumberingTest::BBDef GlobalValueNumberingTestDiamond::kDiamondBbs[] = {
413 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
414 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
415 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
416 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // Block #3, top of the diamond.
417 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #4, left side.
418 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #5, right side.
419 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // Block #6, bottom.
420 };
421
GlobalValueNumberingTestDiamond()422 GlobalValueNumberingTestDiamond::GlobalValueNumberingTestDiamond()
423 : GlobalValueNumberingTest() {
424 PrepareBasicBlocks(kDiamondBbs);
425 }
426
427 class GlobalValueNumberingTestLoop : public GlobalValueNumberingTest {
428 public:
429 GlobalValueNumberingTestLoop();
430
431 private:
432 static const BBDef kLoopBbs[];
433 };
434
435 const GlobalValueNumberingTest::BBDef GlobalValueNumberingTestLoop::kLoopBbs[] = {
436 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
437 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
438 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
439 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
440 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 4), DEF_PRED2(3, 4)), // "taken" loops to self.
441 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
442 };
443
GlobalValueNumberingTestLoop()444 GlobalValueNumberingTestLoop::GlobalValueNumberingTestLoop()
445 : GlobalValueNumberingTest() {
446 PrepareBasicBlocks(kLoopBbs);
447 }
448
449 class GlobalValueNumberingTestCatch : public GlobalValueNumberingTest {
450 public:
451 GlobalValueNumberingTestCatch();
452
453 private:
454 static const BBDef kCatchBbs[];
455 };
456
457 const GlobalValueNumberingTest::BBDef GlobalValueNumberingTestCatch::kCatchBbs[] = {
458 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
459 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
460 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(6)),
461 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)), // The top.
462 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // The throwing insn.
463 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Catch handler.
464 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 5)), // The merged block.
465 };
466
GlobalValueNumberingTestCatch()467 GlobalValueNumberingTestCatch::GlobalValueNumberingTestCatch()
468 : GlobalValueNumberingTest() {
469 PrepareBasicBlocks(kCatchBbs);
470 // Mark catch handler.
471 BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u);
472 catch_handler->catch_entry = true;
473 // Add successor block info to the check block.
474 BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u);
475 check_bb->successor_block_list_type = kCatch;
476 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*>
477 (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
478 successor_block_info->block = catch_handler->id;
479 check_bb->successor_blocks.push_back(successor_block_info);
480 }
481
482 class GlobalValueNumberingTestTwoConsecutiveLoops : public GlobalValueNumberingTest {
483 public:
484 GlobalValueNumberingTestTwoConsecutiveLoops();
485
486 private:
487 static const BBDef kTwoConsecutiveLoopsBbs[];
488 };
489
490 const GlobalValueNumberingTest::BBDef
491 GlobalValueNumberingTestTwoConsecutiveLoops::kTwoConsecutiveLoopsBbs[] = {
492 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
493 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
494 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(9)),
495 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
496 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 6), DEF_PRED2(3, 5)), // "taken" skips over the loop.
497 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(4)),
498 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(4)),
499 DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED2(6, 8)), // "taken" skips over the loop.
500 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(7)),
501 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(7)),
502 };
503
GlobalValueNumberingTestTwoConsecutiveLoops()504 GlobalValueNumberingTestTwoConsecutiveLoops::GlobalValueNumberingTestTwoConsecutiveLoops()
505 : GlobalValueNumberingTest() {
506 PrepareBasicBlocks(kTwoConsecutiveLoopsBbs);
507 }
508
509 class GlobalValueNumberingTestTwoNestedLoops : public GlobalValueNumberingTest {
510 public:
511 GlobalValueNumberingTestTwoNestedLoops();
512
513 private:
514 static const BBDef kTwoNestedLoopsBbs[];
515 };
516
517 const GlobalValueNumberingTest::BBDef
518 GlobalValueNumberingTestTwoNestedLoops::kTwoNestedLoopsBbs[] = {
519 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
520 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
521 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(8)),
522 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
523 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 8), DEF_PRED2(3, 7)), // "taken" skips over the loop.
524 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED2(4, 6)), // "taken" skips over the loop.
525 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(5)),
526 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(5)),
527 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED1(4)),
528 };
529
GlobalValueNumberingTestTwoNestedLoops()530 GlobalValueNumberingTestTwoNestedLoops::GlobalValueNumberingTestTwoNestedLoops()
531 : GlobalValueNumberingTest() {
532 PrepareBasicBlocks(kTwoNestedLoopsBbs);
533 }
534
TEST_F(GlobalValueNumberingTestDiamond,NonAliasingIFields)535 TEST_F(GlobalValueNumberingTestDiamond, NonAliasingIFields) {
536 static const IFieldDef ifields[] = {
537 { 0u, 1u, 0u, false, kDexMemAccessWord },
538 { 1u, 1u, 1u, false, kDexMemAccessWord },
539 { 2u, 1u, 2u, false, kDexMemAccessWord },
540 { 3u, 1u, 3u, false, kDexMemAccessWord },
541 { 4u, 1u, 4u, false, kDexMemAccessShort },
542 { 5u, 1u, 5u, false, kDexMemAccessChar },
543 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
544 { 7u, 1u, 7u, false, kDexMemAccessWord },
545 { 8u, 0u, 0u, false, kDexMemAccessWord }, // Unresolved.
546 { 9u, 1u, 9u, false, kDexMemAccessWord },
547 { 10u, 1u, 10u, false, kDexMemAccessWord },
548 { 11u, 1u, 11u, false, kDexMemAccessWord },
549 };
550 static const MIRDef mirs[] = {
551 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
552 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 100u),
553 DEF_IGET(3, Instruction::IGET, 1u, 100u, 0u),
554 DEF_IGET(6, Instruction::IGET, 2u, 100u, 0u), // Same as at the top.
555
556 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 200u),
557 DEF_IGET(4, Instruction::IGET, 4u, 200u, 1u),
558 DEF_IGET(6, Instruction::IGET, 5u, 200u, 1u), // Same as at the left side.
559
560 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 300u),
561 DEF_IGET(3, Instruction::IGET, 7u, 300u, 2u),
562 DEF_CONST(5, Instruction::CONST, 8u, 1000),
563 DEF_IPUT(5, Instruction::IPUT, 8u, 300u, 2u),
564 DEF_IGET(6, Instruction::IGET, 10u, 300u, 2u), // Differs from the top and the CONST.
565
566 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 400u),
567 DEF_IGET(3, Instruction::IGET, 12u, 400u, 3u),
568 DEF_CONST(3, Instruction::CONST, 13u, 2000),
569 DEF_IPUT(4, Instruction::IPUT, 13u, 400u, 3u),
570 DEF_IPUT(5, Instruction::IPUT, 13u, 400u, 3u),
571 DEF_IGET(6, Instruction::IGET, 16u, 400u, 3u), // Differs from the top, equals the CONST.
572
573 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 500u),
574 DEF_IGET(3, Instruction::IGET_SHORT, 18u, 500u, 4u),
575 DEF_IGET(3, Instruction::IGET_CHAR, 19u, 500u, 5u),
576 DEF_IPUT(4, Instruction::IPUT_SHORT, 20u, 500u, 6u), // Clobbers field #4, not #5.
577 DEF_IGET(6, Instruction::IGET_SHORT, 21u, 500u, 4u), // Differs from the top.
578 DEF_IGET(6, Instruction::IGET_CHAR, 22u, 500u, 5u), // Same as the top.
579
580 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 600u),
581 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 601u),
582 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 602u),
583 DEF_IGET(3, Instruction::IGET, 26u, 600u, 7u),
584 DEF_IGET(3, Instruction::IGET, 27u, 601u, 7u),
585 DEF_IPUT(4, Instruction::IPUT, 28u, 602u, 8u), // Doesn't clobber field #7 for other refs.
586 DEF_IGET(6, Instruction::IGET, 29u, 600u, 7u), // Same as the top.
587 DEF_IGET(6, Instruction::IGET, 30u, 601u, 7u), // Same as the top.
588
589 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 700u),
590 DEF_CONST(4, Instruction::CONST, 32u, 3000),
591 DEF_IPUT(4, Instruction::IPUT, 32u, 700u, 9u),
592 DEF_IPUT(4, Instruction::IPUT, 32u, 700u, 10u),
593 DEF_CONST(5, Instruction::CONST, 35u, 3001),
594 DEF_IPUT(5, Instruction::IPUT, 35u, 700u, 9u),
595 DEF_IPUT(5, Instruction::IPUT, 35u, 700u, 10u),
596 DEF_IGET(6, Instruction::IGET, 38u, 700u, 9u),
597 DEF_IGET(6, Instruction::IGET, 39u, 700u, 10u), // Same value as read from field #9.
598
599 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 800u),
600 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 801u),
601 DEF_CONST(4, Instruction::CONST, 42u, 3000),
602 DEF_IPUT(4, Instruction::IPUT, 42u, 800u, 11u),
603 DEF_IPUT(4, Instruction::IPUT, 42u, 801u, 11u),
604 DEF_CONST(5, Instruction::CONST, 45u, 3001),
605 DEF_IPUT(5, Instruction::IPUT, 45u, 800u, 11u),
606 DEF_IPUT(5, Instruction::IPUT, 45u, 801u, 11u),
607 DEF_IGET(6, Instruction::IGET, 48u, 800u, 11u),
608 DEF_IGET(6, Instruction::IGET, 49u, 801u, 11u), // Same value as read from ref 46u.
609
610 // Invoke doesn't interfere with non-aliasing refs. There's one test above where a reference
611 // escapes in the left BB (we let a reference escape if we use it to store to an unresolved
612 // field) and the INVOKE in the right BB shouldn't interfere with that either.
613 DEF_INVOKE1(5, Instruction::INVOKE_STATIC, 48u),
614 };
615
616 PrepareIFields(ifields);
617 PrepareMIRs(mirs);
618 PerformGVN();
619 ASSERT_EQ(arraysize(mirs), value_names_.size());
620 EXPECT_EQ(value_names_[1], value_names_[2]);
621
622 EXPECT_EQ(value_names_[4], value_names_[5]);
623
624 EXPECT_NE(value_names_[7], value_names_[10]);
625 EXPECT_NE(value_names_[8], value_names_[10]);
626
627 EXPECT_NE(value_names_[12], value_names_[16]);
628 EXPECT_EQ(value_names_[13], value_names_[16]);
629
630 EXPECT_NE(value_names_[18], value_names_[21]);
631 EXPECT_EQ(value_names_[19], value_names_[22]);
632
633 EXPECT_EQ(value_names_[26], value_names_[29]);
634 EXPECT_EQ(value_names_[27], value_names_[30]);
635
636 EXPECT_EQ(value_names_[38], value_names_[39]);
637
638 EXPECT_EQ(value_names_[48], value_names_[49]);
639 }
640
TEST_F(GlobalValueNumberingTestDiamond,AliasingIFieldsSingleObject)641 TEST_F(GlobalValueNumberingTestDiamond, AliasingIFieldsSingleObject) {
642 static const IFieldDef ifields[] = {
643 { 0u, 1u, 0u, false, kDexMemAccessWord },
644 { 1u, 1u, 1u, false, kDexMemAccessWord },
645 { 2u, 1u, 2u, false, kDexMemAccessWord },
646 { 3u, 1u, 3u, false, kDexMemAccessWord },
647 { 4u, 1u, 4u, false, kDexMemAccessShort },
648 { 5u, 1u, 5u, false, kDexMemAccessChar },
649 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
650 { 7u, 1u, 7u, false, kDexMemAccessWord },
651 { 8u, 1u, 8u, false, kDexMemAccessWord },
652 };
653 static const MIRDef mirs[] = {
654 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
655 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u),
656 DEF_IGET(6, Instruction::IGET, 1u, 100u, 0u), // Same as at the top.
657
658 DEF_IGET(4, Instruction::IGET, 2u, 100u, 1u),
659 DEF_IGET(6, Instruction::IGET, 3u, 100u, 1u), // Same as at the left side.
660
661 DEF_IGET(3, Instruction::IGET, 4u, 100u, 2u),
662 DEF_CONST(5, Instruction::CONST, 5u, 1000),
663 DEF_IPUT(5, Instruction::IPUT, 5u, 100u, 2u),
664 DEF_IGET(6, Instruction::IGET, 7u, 100u, 2u), // Differs from the top and the CONST.
665
666 DEF_IGET(3, Instruction::IGET, 8u, 100u, 3u),
667 DEF_CONST(3, Instruction::CONST, 9u, 2000),
668 DEF_IPUT(4, Instruction::IPUT, 9u, 100u, 3u),
669 DEF_IPUT(5, Instruction::IPUT, 9u, 100u, 3u),
670 DEF_IGET(6, Instruction::IGET, 12u, 100u, 3u), // Differs from the top, equals the CONST.
671
672 DEF_IGET(3, Instruction::IGET_SHORT, 13u, 100u, 4u),
673 DEF_IGET(3, Instruction::IGET_CHAR, 14u, 100u, 5u),
674 DEF_IPUT(4, Instruction::IPUT_SHORT, 15u, 100u, 6u), // Clobbers field #4, not #5.
675 DEF_IGET(6, Instruction::IGET_SHORT, 16u, 100u, 4u), // Differs from the top.
676 DEF_IGET(6, Instruction::IGET_CHAR, 17u, 100u, 5u), // Same as the top.
677
678 DEF_CONST(4, Instruction::CONST, 18u, 3000),
679 DEF_IPUT(4, Instruction::IPUT, 18u, 100u, 7u),
680 DEF_IPUT(4, Instruction::IPUT, 18u, 100u, 8u),
681 DEF_CONST(5, Instruction::CONST, 21u, 3001),
682 DEF_IPUT(5, Instruction::IPUT, 21u, 100u, 7u),
683 DEF_IPUT(5, Instruction::IPUT, 21u, 100u, 8u),
684 DEF_IGET(6, Instruction::IGET, 24u, 100u, 7u),
685 DEF_IGET(6, Instruction::IGET, 25u, 100u, 8u), // Same value as read from field #7.
686 };
687
688 PrepareIFields(ifields);
689 PrepareMIRs(mirs);
690 PerformGVN();
691 ASSERT_EQ(arraysize(mirs), value_names_.size());
692 EXPECT_EQ(value_names_[0], value_names_[1]);
693
694 EXPECT_EQ(value_names_[2], value_names_[3]);
695
696 EXPECT_NE(value_names_[4], value_names_[7]);
697 EXPECT_NE(value_names_[5], value_names_[7]);
698
699 EXPECT_NE(value_names_[8], value_names_[12]);
700 EXPECT_EQ(value_names_[9], value_names_[12]);
701
702 EXPECT_NE(value_names_[13], value_names_[16]);
703 EXPECT_EQ(value_names_[14], value_names_[17]);
704
705 EXPECT_EQ(value_names_[24], value_names_[25]);
706 }
707
TEST_F(GlobalValueNumberingTestDiamond,AliasingIFieldsTwoObjects)708 TEST_F(GlobalValueNumberingTestDiamond, AliasingIFieldsTwoObjects) {
709 static const IFieldDef ifields[] = {
710 { 0u, 1u, 0u, false, kDexMemAccessWord },
711 { 1u, 1u, 1u, false, kDexMemAccessWord },
712 { 2u, 1u, 2u, false, kDexMemAccessWord },
713 { 3u, 1u, 3u, false, kDexMemAccessWord },
714 { 4u, 1u, 4u, false, kDexMemAccessShort },
715 { 5u, 1u, 5u, false, kDexMemAccessChar },
716 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
717 { 7u, 1u, 7u, false, kDexMemAccessWord },
718 { 8u, 1u, 8u, false, kDexMemAccessWord },
719 };
720 static const MIRDef mirs[] = {
721 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
722 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u),
723 DEF_IPUT(4, Instruction::IPUT, 1u, 101u, 0u), // May alias with the IGET at the top.
724 DEF_IGET(6, Instruction::IGET, 2u, 100u, 0u), // Differs from the top.
725
726 DEF_IGET(3, Instruction::IGET, 3u, 100u, 1u),
727 DEF_IPUT(5, Instruction::IPUT, 3u, 101u, 1u), // If aliasing, stores the same value.
728 DEF_IGET(6, Instruction::IGET, 5u, 100u, 1u), // Same as the top.
729
730 DEF_IGET(3, Instruction::IGET, 6u, 100u, 2u),
731 DEF_CONST(5, Instruction::CONST, 7u, 1000),
732 DEF_IPUT(5, Instruction::IPUT, 7u, 101u, 2u),
733 DEF_IGET(6, Instruction::IGET, 9u, 100u, 2u), // Differs from the top and the CONST.
734
735 DEF_IGET(3, Instruction::IGET, 10u, 100u, 3u),
736 DEF_CONST(3, Instruction::CONST, 11u, 2000),
737 DEF_IPUT(4, Instruction::IPUT, 11u, 101u, 3u),
738 DEF_IPUT(5, Instruction::IPUT, 11u, 101u, 3u),
739 DEF_IGET(6, Instruction::IGET, 14u, 100u, 3u), // Differs from the top and the CONST.
740
741 DEF_IGET(3, Instruction::IGET_SHORT, 15u, 100u, 4u),
742 DEF_IGET(3, Instruction::IGET_CHAR, 16u, 100u, 5u),
743 DEF_IPUT(4, Instruction::IPUT_SHORT, 17u, 101u, 6u), // Clobbers field #4, not #5.
744 DEF_IGET(6, Instruction::IGET_SHORT, 18u, 100u, 4u), // Differs from the top.
745 DEF_IGET(6, Instruction::IGET_CHAR, 19u, 100u, 5u), // Same as the top.
746
747 DEF_CONST(4, Instruction::CONST, 20u, 3000),
748 DEF_IPUT(4, Instruction::IPUT, 20u, 100u, 7u),
749 DEF_IPUT(4, Instruction::IPUT, 20u, 101u, 8u),
750 DEF_CONST(5, Instruction::CONST, 23u, 3001),
751 DEF_IPUT(5, Instruction::IPUT, 23u, 100u, 7u),
752 DEF_IPUT(5, Instruction::IPUT, 23u, 101u, 8u),
753 DEF_IGET(6, Instruction::IGET, 26u, 100u, 7u),
754 DEF_IGET(6, Instruction::IGET, 27u, 101u, 8u), // Same value as read from field #7.
755 };
756
757 PrepareIFields(ifields);
758 PrepareMIRs(mirs);
759 PerformGVN();
760 ASSERT_EQ(arraysize(mirs), value_names_.size());
761 EXPECT_NE(value_names_[0], value_names_[2]);
762
763 EXPECT_EQ(value_names_[3], value_names_[5]);
764
765 EXPECT_NE(value_names_[6], value_names_[9]);
766 EXPECT_NE(value_names_[7], value_names_[9]);
767
768 EXPECT_NE(value_names_[10], value_names_[14]);
769 EXPECT_NE(value_names_[10], value_names_[14]);
770
771 EXPECT_NE(value_names_[15], value_names_[18]);
772 EXPECT_EQ(value_names_[16], value_names_[19]);
773
774 EXPECT_EQ(value_names_[26], value_names_[27]);
775 }
776
TEST_F(GlobalValueNumberingTestDiamond,SFields)777 TEST_F(GlobalValueNumberingTestDiamond, SFields) {
778 static const SFieldDef sfields[] = {
779 { 0u, 1u, 0u, false, kDexMemAccessWord },
780 { 1u, 1u, 1u, false, kDexMemAccessWord },
781 { 2u, 1u, 2u, false, kDexMemAccessWord },
782 { 3u, 1u, 3u, false, kDexMemAccessWord },
783 { 4u, 1u, 4u, false, kDexMemAccessShort },
784 { 5u, 1u, 5u, false, kDexMemAccessChar },
785 { 6u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
786 { 7u, 1u, 7u, false, kDexMemAccessWord },
787 { 8u, 1u, 8u, false, kDexMemAccessWord },
788 };
789 static const MIRDef mirs[] = {
790 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
791 DEF_SGET(3, Instruction::SGET, 0u, 0u),
792 DEF_SGET(6, Instruction::SGET, 1u, 0u), // Same as at the top.
793
794 DEF_SGET(4, Instruction::SGET, 2u, 1u),
795 DEF_SGET(6, Instruction::SGET, 3u, 1u), // Same as at the left side.
796
797 DEF_SGET(3, Instruction::SGET, 4u, 2u),
798 DEF_CONST(5, Instruction::CONST, 5u, 100),
799 DEF_SPUT(5, Instruction::SPUT, 5u, 2u),
800 DEF_SGET(6, Instruction::SGET, 7u, 2u), // Differs from the top and the CONST.
801
802 DEF_SGET(3, Instruction::SGET, 8u, 3u),
803 DEF_CONST(3, Instruction::CONST, 9u, 200),
804 DEF_SPUT(4, Instruction::SPUT, 9u, 3u),
805 DEF_SPUT(5, Instruction::SPUT, 9u, 3u),
806 DEF_SGET(6, Instruction::SGET, 12u, 3u), // Differs from the top, equals the CONST.
807
808 DEF_SGET(3, Instruction::SGET_SHORT, 13u, 4u),
809 DEF_SGET(3, Instruction::SGET_CHAR, 14u, 5u),
810 DEF_SPUT(4, Instruction::SPUT_SHORT, 15u, 6u), // Clobbers field #4, not #5.
811 DEF_SGET(6, Instruction::SGET_SHORT, 16u, 4u), // Differs from the top.
812 DEF_SGET(6, Instruction::SGET_CHAR, 17u, 5u), // Same as the top.
813
814 DEF_CONST(4, Instruction::CONST, 18u, 300),
815 DEF_SPUT(4, Instruction::SPUT, 18u, 7u),
816 DEF_SPUT(4, Instruction::SPUT, 18u, 8u),
817 DEF_CONST(5, Instruction::CONST, 21u, 301),
818 DEF_SPUT(5, Instruction::SPUT, 21u, 7u),
819 DEF_SPUT(5, Instruction::SPUT, 21u, 8u),
820 DEF_SGET(6, Instruction::SGET, 24u, 7u),
821 DEF_SGET(6, Instruction::SGET, 25u, 8u), // Same value as read from field #7.
822 };
823
824 PrepareSFields(sfields);
825 PrepareMIRs(mirs);
826 PerformGVN();
827 ASSERT_EQ(arraysize(mirs), value_names_.size());
828 EXPECT_EQ(value_names_[0], value_names_[1]);
829
830 EXPECT_EQ(value_names_[2], value_names_[3]);
831
832 EXPECT_NE(value_names_[4], value_names_[7]);
833 EXPECT_NE(value_names_[5], value_names_[7]);
834
835 EXPECT_NE(value_names_[8], value_names_[12]);
836 EXPECT_EQ(value_names_[9], value_names_[12]);
837
838 EXPECT_NE(value_names_[13], value_names_[16]);
839 EXPECT_EQ(value_names_[14], value_names_[17]);
840
841 EXPECT_EQ(value_names_[24], value_names_[25]);
842 }
843
TEST_F(GlobalValueNumberingTestDiamond,NonAliasingArrays)844 TEST_F(GlobalValueNumberingTestDiamond, NonAliasingArrays) {
845 static const MIRDef mirs[] = {
846 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
847 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 100u),
848 DEF_AGET(3, Instruction::AGET, 1u, 100u, 101u),
849 DEF_AGET(6, Instruction::AGET, 2u, 100u, 101u), // Same as at the top.
850
851 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u),
852 DEF_IGET(4, Instruction::AGET, 4u, 200u, 201u),
853 DEF_IGET(6, Instruction::AGET, 5u, 200u, 201u), // Same as at the left side.
854
855 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 300u),
856 DEF_AGET(3, Instruction::AGET, 7u, 300u, 301u),
857 DEF_CONST(5, Instruction::CONST, 8u, 1000),
858 DEF_APUT(5, Instruction::APUT, 8u, 300u, 301u),
859 DEF_AGET(6, Instruction::AGET, 10u, 300u, 301u), // Differs from the top and the CONST.
860
861 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 400u),
862 DEF_AGET(3, Instruction::AGET, 12u, 400u, 401u),
863 DEF_CONST(3, Instruction::CONST, 13u, 2000),
864 DEF_APUT(4, Instruction::APUT, 13u, 400u, 401u),
865 DEF_APUT(5, Instruction::APUT, 13u, 400u, 401u),
866 DEF_AGET(6, Instruction::AGET, 16u, 400u, 401u), // Differs from the top, equals the CONST.
867
868 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 500u),
869 DEF_AGET(3, Instruction::AGET, 18u, 500u, 501u),
870 DEF_APUT(4, Instruction::APUT, 19u, 500u, 502u), // Clobbers value at index 501u.
871 DEF_AGET(6, Instruction::AGET, 20u, 500u, 501u), // Differs from the top.
872
873 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 600u),
874 DEF_CONST(4, Instruction::CONST, 22u, 3000),
875 DEF_APUT(4, Instruction::APUT, 22u, 600u, 601u),
876 DEF_APUT(4, Instruction::APUT, 22u, 600u, 602u),
877 DEF_CONST(5, Instruction::CONST, 25u, 3001),
878 DEF_APUT(5, Instruction::APUT, 25u, 600u, 601u),
879 DEF_APUT(5, Instruction::APUT, 25u, 600u, 602u),
880 DEF_AGET(6, Instruction::AGET, 28u, 600u, 601u),
881 DEF_AGET(6, Instruction::AGET, 29u, 600u, 602u), // Same value as read from index 601u.
882
883 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 700u),
884 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 701u),
885 DEF_AGET(3, Instruction::AGET, 32u, 700u, 702u),
886 DEF_APUT(4, Instruction::APUT, 33u, 701u, 702u), // Doesn't interfere with unrelated array.
887 DEF_AGET(6, Instruction::AGET, 34u, 700u, 702u), // Same value as at the top.
888 };
889
890 PrepareMIRs(mirs);
891 PerformGVN();
892 ASSERT_EQ(arraysize(mirs), value_names_.size());
893 EXPECT_EQ(value_names_[1], value_names_[2]);
894
895 EXPECT_EQ(value_names_[4], value_names_[5]);
896
897 EXPECT_NE(value_names_[7], value_names_[10]);
898 EXPECT_NE(value_names_[8], value_names_[10]);
899
900 EXPECT_NE(value_names_[12], value_names_[16]);
901 EXPECT_EQ(value_names_[13], value_names_[16]);
902
903 EXPECT_NE(value_names_[18], value_names_[20]);
904
905 EXPECT_NE(value_names_[28], value_names_[22]);
906 EXPECT_NE(value_names_[28], value_names_[25]);
907 EXPECT_EQ(value_names_[28], value_names_[29]);
908
909 EXPECT_EQ(value_names_[32], value_names_[34]);
910 }
911
TEST_F(GlobalValueNumberingTestDiamond,AliasingArrays)912 TEST_F(GlobalValueNumberingTestDiamond, AliasingArrays) {
913 static const MIRDef mirs[] = {
914 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
915 // NOTE: We're also testing that these tests really do not interfere with each other.
916
917 DEF_AGET(3, Instruction::AGET_BOOLEAN, 0u, 100u, 101u),
918 DEF_AGET(6, Instruction::AGET_BOOLEAN, 1u, 100u, 101u), // Same as at the top.
919
920 DEF_IGET(4, Instruction::AGET_OBJECT, 2u, 200u, 201u),
921 DEF_IGET(6, Instruction::AGET_OBJECT, 3u, 200u, 201u), // Same as at the left side.
922
923 DEF_AGET(3, Instruction::AGET_WIDE, 4u, 300u, 301u),
924 DEF_CONST(5, Instruction::CONST_WIDE, 6u, 1000),
925 DEF_APUT(5, Instruction::APUT_WIDE, 6u, 300u, 301u),
926 DEF_AGET(6, Instruction::AGET_WIDE, 8u, 300u, 301u), // Differs from the top and the CONST.
927
928 DEF_AGET(3, Instruction::AGET_SHORT, 10u, 400u, 401u),
929 DEF_CONST(3, Instruction::CONST, 11u, 2000),
930 DEF_APUT(4, Instruction::APUT_SHORT, 11u, 400u, 401u),
931 DEF_APUT(5, Instruction::APUT_SHORT, 11u, 400u, 401u),
932 DEF_AGET(6, Instruction::AGET_SHORT, 12u, 400u, 401u), // Differs from the top, == CONST.
933
934 DEF_AGET(3, Instruction::AGET_CHAR, 13u, 500u, 501u),
935 DEF_APUT(4, Instruction::APUT_CHAR, 14u, 500u, 502u), // Clobbers value at index 501u.
936 DEF_AGET(6, Instruction::AGET_CHAR, 15u, 500u, 501u), // Differs from the top.
937
938 DEF_AGET(3, Instruction::AGET_BYTE, 16u, 600u, 602u),
939 DEF_APUT(4, Instruction::APUT_BYTE, 17u, 601u, 602u), // Clobbers values in array 600u.
940 DEF_AGET(6, Instruction::AGET_BYTE, 18u, 600u, 602u), // Differs from the top.
941
942 DEF_CONST(4, Instruction::CONST, 19u, 3000),
943 DEF_APUT(4, Instruction::APUT, 19u, 700u, 701u),
944 DEF_APUT(4, Instruction::APUT, 19u, 700u, 702u),
945 DEF_CONST(5, Instruction::CONST, 22u, 3001),
946 DEF_APUT(5, Instruction::APUT, 22u, 700u, 701u),
947 DEF_APUT(5, Instruction::APUT, 22u, 700u, 702u),
948 DEF_AGET(6, Instruction::AGET, 25u, 700u, 701u),
949 DEF_AGET(6, Instruction::AGET, 26u, 700u, 702u), // Same value as read from index 601u.
950 };
951
952 PrepareMIRs(mirs);
953 static const int32_t wide_sregs[] = { 4, 6, 8 };
954 MarkAsWideSRegs(wide_sregs);
955 PerformGVN();
956 ASSERT_EQ(arraysize(mirs), value_names_.size());
957 EXPECT_EQ(value_names_[0], value_names_[1]);
958
959 EXPECT_EQ(value_names_[2], value_names_[3]);
960
961 EXPECT_NE(value_names_[4], value_names_[7]);
962 EXPECT_NE(value_names_[5], value_names_[7]);
963
964 EXPECT_NE(value_names_[8], value_names_[12]);
965 EXPECT_EQ(value_names_[9], value_names_[12]);
966
967 EXPECT_NE(value_names_[13], value_names_[15]);
968
969 EXPECT_NE(value_names_[16], value_names_[18]);
970
971 EXPECT_NE(value_names_[25], value_names_[19]);
972 EXPECT_NE(value_names_[25], value_names_[22]);
973 EXPECT_EQ(value_names_[25], value_names_[26]);
974 }
975
TEST_F(GlobalValueNumberingTestDiamond,Phi)976 TEST_F(GlobalValueNumberingTestDiamond, Phi) {
977 static const MIRDef mirs[] = {
978 DEF_CONST(3, Instruction::CONST, 0u, 1000),
979 DEF_CONST(4, Instruction::CONST, 1u, 2000),
980 DEF_CONST(5, Instruction::CONST, 2u, 3000),
981 DEF_MOVE(4, Instruction::MOVE, 3u, 0u),
982 DEF_MOVE(4, Instruction::MOVE, 4u, 1u),
983 DEF_MOVE(5, Instruction::MOVE, 5u, 0u),
984 DEF_MOVE(5, Instruction::MOVE, 6u, 2u),
985 DEF_PHI2(6, 7u, 3u, 5u), // Same as CONST 0u (1000).
986 DEF_PHI2(6, 8u, 3u, 0u), // Same as CONST 0u (1000).
987 DEF_PHI2(6, 9u, 0u, 5u), // Same as CONST 0u (1000).
988 DEF_PHI2(6, 10u, 4u, 5u), // Merge 1u (2000) and 0u (1000).
989 DEF_PHI2(6, 11u, 1u, 5u), // Merge 1u (2000) and 0u (1000).
990 DEF_PHI2(6, 12u, 4u, 0u), // Merge 1u (2000) and 0u (1000).
991 DEF_PHI2(6, 13u, 1u, 0u), // Merge 1u (2000) and 0u (1000).
992 DEF_PHI2(6, 14u, 3u, 6u), // Merge 0u (1000) and 2u (3000).
993 DEF_PHI2(6, 15u, 0u, 6u), // Merge 0u (1000) and 2u (3000).
994 DEF_PHI2(6, 16u, 3u, 2u), // Merge 0u (1000) and 2u (3000).
995 DEF_PHI2(6, 17u, 0u, 2u), // Merge 0u (1000) and 2u (3000).
996 DEF_PHI2(6, 18u, 4u, 6u), // Merge 1u (2000) and 2u (3000).
997 DEF_PHI2(6, 19u, 1u, 6u), // Merge 1u (2000) and 2u (3000).
998 DEF_PHI2(6, 20u, 4u, 2u), // Merge 1u (2000) and 2u (3000).
999 DEF_PHI2(6, 21u, 1u, 2u), // Merge 1u (2000) and 2u (3000).
1000 };
1001
1002 PrepareMIRs(mirs);
1003 PerformGVN();
1004 ASSERT_EQ(arraysize(mirs), value_names_.size());
1005 EXPECT_EQ(value_names_[0], value_names_[7]);
1006 EXPECT_EQ(value_names_[0], value_names_[8]);
1007 EXPECT_EQ(value_names_[0], value_names_[9]);
1008 EXPECT_NE(value_names_[10], value_names_[0]);
1009 EXPECT_NE(value_names_[10], value_names_[1]);
1010 EXPECT_NE(value_names_[10], value_names_[2]);
1011 EXPECT_EQ(value_names_[10], value_names_[11]);
1012 EXPECT_EQ(value_names_[10], value_names_[12]);
1013 EXPECT_EQ(value_names_[10], value_names_[13]);
1014 EXPECT_NE(value_names_[14], value_names_[0]);
1015 EXPECT_NE(value_names_[14], value_names_[1]);
1016 EXPECT_NE(value_names_[14], value_names_[2]);
1017 EXPECT_NE(value_names_[14], value_names_[10]);
1018 EXPECT_EQ(value_names_[14], value_names_[15]);
1019 EXPECT_EQ(value_names_[14], value_names_[16]);
1020 EXPECT_EQ(value_names_[14], value_names_[17]);
1021 EXPECT_NE(value_names_[18], value_names_[0]);
1022 EXPECT_NE(value_names_[18], value_names_[1]);
1023 EXPECT_NE(value_names_[18], value_names_[2]);
1024 EXPECT_NE(value_names_[18], value_names_[10]);
1025 EXPECT_NE(value_names_[18], value_names_[14]);
1026 EXPECT_EQ(value_names_[18], value_names_[19]);
1027 EXPECT_EQ(value_names_[18], value_names_[20]);
1028 EXPECT_EQ(value_names_[18], value_names_[21]);
1029 }
1030
TEST_F(GlobalValueNumberingTestDiamond,PhiWide)1031 TEST_F(GlobalValueNumberingTestDiamond, PhiWide) {
1032 static const MIRDef mirs[] = {
1033 DEF_CONST_WIDE(3, Instruction::CONST_WIDE, 0u, 1000),
1034 DEF_CONST_WIDE(4, Instruction::CONST_WIDE, 2u, 2000),
1035 DEF_CONST_WIDE(5, Instruction::CONST_WIDE, 4u, 3000),
1036 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 6u, 0u),
1037 DEF_MOVE_WIDE(4, Instruction::MOVE_WIDE, 8u, 2u),
1038 DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 10u, 0u),
1039 DEF_MOVE_WIDE(5, Instruction::MOVE_WIDE, 12u, 4u),
1040 DEF_PHI2(6, 14u, 6u, 10u), // Same as CONST_WIDE 0u (1000).
1041 DEF_PHI2(6, 15u, 7u, 11u), // Same as CONST_WIDE 0u (1000), high word.
1042 DEF_PHI2(6, 16u, 6u, 0u), // Same as CONST_WIDE 0u (1000).
1043 DEF_PHI2(6, 17u, 7u, 1u), // Same as CONST_WIDE 0u (1000), high word.
1044 DEF_PHI2(6, 18u, 0u, 10u), // Same as CONST_WIDE 0u (1000).
1045 DEF_PHI2(6, 19u, 1u, 11u), // Same as CONST_WIDE 0u (1000), high word.
1046 DEF_PHI2(6, 20u, 8u, 10u), // Merge 2u (2000) and 0u (1000).
1047 DEF_PHI2(6, 21u, 9u, 11u), // Merge 2u (2000) and 0u (1000), high word.
1048 DEF_PHI2(6, 22u, 2u, 10u), // Merge 2u (2000) and 0u (1000).
1049 DEF_PHI2(6, 23u, 3u, 11u), // Merge 2u (2000) and 0u (1000), high word.
1050 DEF_PHI2(6, 24u, 8u, 0u), // Merge 2u (2000) and 0u (1000).
1051 DEF_PHI2(6, 25u, 9u, 1u), // Merge 2u (2000) and 0u (1000), high word.
1052 DEF_PHI2(6, 26u, 2u, 0u), // Merge 2u (2000) and 0u (1000).
1053 DEF_PHI2(6, 27u, 5u, 1u), // Merge 2u (2000) and 0u (1000), high word.
1054 DEF_PHI2(6, 28u, 6u, 12u), // Merge 0u (1000) and 4u (3000).
1055 DEF_PHI2(6, 29u, 7u, 13u), // Merge 0u (1000) and 4u (3000), high word.
1056 DEF_PHI2(6, 30u, 0u, 12u), // Merge 0u (1000) and 4u (3000).
1057 DEF_PHI2(6, 31u, 1u, 13u), // Merge 0u (1000) and 4u (3000), high word.
1058 DEF_PHI2(6, 32u, 6u, 4u), // Merge 0u (1000) and 4u (3000).
1059 DEF_PHI2(6, 33u, 7u, 5u), // Merge 0u (1000) and 4u (3000), high word.
1060 DEF_PHI2(6, 34u, 0u, 4u), // Merge 0u (1000) and 4u (3000).
1061 DEF_PHI2(6, 35u, 1u, 5u), // Merge 0u (1000) and 4u (3000), high word.
1062 DEF_PHI2(6, 36u, 8u, 12u), // Merge 2u (2000) and 4u (3000).
1063 DEF_PHI2(6, 37u, 9u, 13u), // Merge 2u (2000) and 4u (3000), high word.
1064 DEF_PHI2(6, 38u, 2u, 12u), // Merge 2u (2000) and 4u (3000).
1065 DEF_PHI2(6, 39u, 3u, 13u), // Merge 2u (2000) and 4u (3000), high word.
1066 DEF_PHI2(6, 40u, 8u, 4u), // Merge 2u (2000) and 4u (3000).
1067 DEF_PHI2(6, 41u, 9u, 5u), // Merge 2u (2000) and 4u (3000), high word.
1068 DEF_PHI2(6, 42u, 2u, 4u), // Merge 2u (2000) and 4u (3000).
1069 DEF_PHI2(6, 43u, 3u, 5u), // Merge 2u (2000) and 4u (3000), high word.
1070 };
1071
1072 PrepareMIRs(mirs);
1073 for (size_t i = 0u; i != arraysize(mirs); ++i) {
1074 if ((mirs_[i].ssa_rep->defs[0] % 2) == 0) {
1075 const int32_t wide_sregs[] = { mirs_[i].ssa_rep->defs[0] };
1076 MarkAsWideSRegs(wide_sregs);
1077 }
1078 }
1079 PerformGVN();
1080 ASSERT_EQ(arraysize(mirs), value_names_.size());
1081 EXPECT_EQ(value_names_[0], value_names_[7]);
1082 EXPECT_EQ(value_names_[0], value_names_[9]);
1083 EXPECT_EQ(value_names_[0], value_names_[11]);
1084 EXPECT_NE(value_names_[13], value_names_[0]);
1085 EXPECT_NE(value_names_[13], value_names_[1]);
1086 EXPECT_NE(value_names_[13], value_names_[2]);
1087 EXPECT_EQ(value_names_[13], value_names_[15]);
1088 EXPECT_EQ(value_names_[13], value_names_[17]);
1089 EXPECT_EQ(value_names_[13], value_names_[19]);
1090 EXPECT_NE(value_names_[21], value_names_[0]);
1091 EXPECT_NE(value_names_[21], value_names_[1]);
1092 EXPECT_NE(value_names_[21], value_names_[2]);
1093 EXPECT_NE(value_names_[21], value_names_[13]);
1094 EXPECT_EQ(value_names_[21], value_names_[23]);
1095 EXPECT_EQ(value_names_[21], value_names_[25]);
1096 EXPECT_EQ(value_names_[21], value_names_[27]);
1097 EXPECT_NE(value_names_[29], value_names_[0]);
1098 EXPECT_NE(value_names_[29], value_names_[1]);
1099 EXPECT_NE(value_names_[29], value_names_[2]);
1100 EXPECT_NE(value_names_[29], value_names_[13]);
1101 EXPECT_NE(value_names_[29], value_names_[21]);
1102 EXPECT_EQ(value_names_[29], value_names_[31]);
1103 EXPECT_EQ(value_names_[29], value_names_[33]);
1104 EXPECT_EQ(value_names_[29], value_names_[35]);
1105 // High words should get kNoValue.
1106 EXPECT_EQ(value_names_[8], kNoValue);
1107 EXPECT_EQ(value_names_[10], kNoValue);
1108 EXPECT_EQ(value_names_[12], kNoValue);
1109 EXPECT_EQ(value_names_[14], kNoValue);
1110 EXPECT_EQ(value_names_[16], kNoValue);
1111 EXPECT_EQ(value_names_[18], kNoValue);
1112 EXPECT_EQ(value_names_[20], kNoValue);
1113 EXPECT_EQ(value_names_[22], kNoValue);
1114 EXPECT_EQ(value_names_[24], kNoValue);
1115 EXPECT_EQ(value_names_[26], kNoValue);
1116 EXPECT_EQ(value_names_[28], kNoValue);
1117 EXPECT_EQ(value_names_[30], kNoValue);
1118 EXPECT_EQ(value_names_[32], kNoValue);
1119 EXPECT_EQ(value_names_[34], kNoValue);
1120 EXPECT_EQ(value_names_[36], kNoValue);
1121 }
1122
TEST_F(GlobalValueNumberingTestLoop,NonAliasingIFields)1123 TEST_F(GlobalValueNumberingTestLoop, NonAliasingIFields) {
1124 static const IFieldDef ifields[] = {
1125 { 0u, 1u, 0u, false, kDexMemAccessWord },
1126 { 1u, 1u, 1u, false, kDexMemAccessWord },
1127 { 2u, 1u, 2u, false, kDexMemAccessWord },
1128 { 3u, 1u, 3u, false, kDexMemAccessWord },
1129 { 4u, 1u, 4u, false, kDexMemAccessWord },
1130 { 5u, 1u, 5u, false, kDexMemAccessShort },
1131 { 6u, 1u, 6u, false, kDexMemAccessChar },
1132 { 7u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
1133 { 8u, 1u, 8u, false, kDexMemAccessWord },
1134 { 9u, 0u, 0u, false, kDexMemAccessWord }, // Unresolved.
1135 { 10u, 1u, 10u, false, kDexMemAccessWord },
1136 { 11u, 1u, 11u, false, kDexMemAccessWord },
1137 };
1138 static const MIRDef mirs[] = {
1139 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
1140 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 100u),
1141 DEF_IGET(3, Instruction::IGET, 1u, 100u, 0u),
1142 DEF_IGET(4, Instruction::IGET, 2u, 100u, 0u), // Same as at the top.
1143 DEF_IGET(5, Instruction::IGET, 3u, 100u, 0u), // Same as at the top.
1144
1145 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 200u),
1146 DEF_IGET(3, Instruction::IGET, 5u, 200u, 1u),
1147 DEF_IGET(4, Instruction::IGET, 6u, 200u, 1u), // Differs from top...
1148 DEF_IPUT(4, Instruction::IPUT, 7u, 200u, 1u), // Because of this IPUT.
1149 DEF_IGET(5, Instruction::IGET, 8u, 200u, 1u), // Differs from top and the loop IGET.
1150
1151 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 300u),
1152 DEF_IGET(3, Instruction::IGET, 10u, 300u, 2u),
1153 DEF_IPUT(4, Instruction::IPUT, 11u, 300u, 2u), // Because of this IPUT...
1154 DEF_IGET(4, Instruction::IGET, 12u, 300u, 2u), // Differs from top.
1155 DEF_IGET(5, Instruction::IGET, 13u, 300u, 2u), // Differs from top but same as the loop IGET.
1156
1157 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 400u),
1158 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 401u),
1159 DEF_CONST(3, Instruction::CONST, 16u, 3000),
1160 DEF_IPUT(3, Instruction::IPUT, 16u, 400u, 3u),
1161 DEF_IPUT(3, Instruction::IPUT, 16u, 400u, 4u),
1162 DEF_IPUT(3, Instruction::IPUT, 16u, 401u, 3u),
1163 DEF_IGET(4, Instruction::IGET, 20u, 400u, 3u), // Differs from 16u and 23u.
1164 DEF_IGET(4, Instruction::IGET, 21u, 400u, 4u), // Same as 20u.
1165 DEF_IGET(4, Instruction::IGET, 22u, 401u, 3u), // Same as 20u.
1166 DEF_CONST(4, Instruction::CONST, 23u, 4000),
1167 DEF_IPUT(4, Instruction::IPUT, 23u, 400u, 3u),
1168 DEF_IPUT(4, Instruction::IPUT, 23u, 400u, 4u),
1169 DEF_IPUT(4, Instruction::IPUT, 23u, 401u, 3u),
1170 DEF_IGET(5, Instruction::IGET, 27u, 400u, 3u), // Differs from 16u and 20u...
1171 DEF_IGET(5, Instruction::IGET, 28u, 400u, 4u), // and same as the CONST 23u
1172 DEF_IGET(5, Instruction::IGET, 29u, 400u, 4u), // and same as the CONST 23u.
1173
1174 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 500u),
1175 DEF_IGET(3, Instruction::IGET_SHORT, 31u, 500u, 5u),
1176 DEF_IGET(3, Instruction::IGET_CHAR, 32u, 500u, 6u),
1177 DEF_IPUT(4, Instruction::IPUT_SHORT, 33u, 500u, 7u), // Clobbers field #5, not #6.
1178 DEF_IGET(5, Instruction::IGET_SHORT, 34u, 500u, 5u), // Differs from the top.
1179 DEF_IGET(5, Instruction::IGET_CHAR, 35u, 500u, 6u), // Same as the top.
1180
1181 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 600u),
1182 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 601u),
1183 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 602u),
1184 DEF_IGET(3, Instruction::IGET, 39u, 600u, 8u),
1185 DEF_IGET(3, Instruction::IGET, 40u, 601u, 8u),
1186 DEF_IPUT(4, Instruction::IPUT, 41u, 602u, 9u), // Doesn't clobber field #8 for other refs.
1187 DEF_IGET(5, Instruction::IGET, 42u, 600u, 8u), // Same as the top.
1188 DEF_IGET(5, Instruction::IGET, 43u, 601u, 8u), // Same as the top.
1189
1190 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 700u),
1191 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 701u),
1192 DEF_CONST(3, Instruction::CONST, 46u, 3000),
1193 DEF_IPUT(3, Instruction::IPUT, 46u, 700u, 10u),
1194 DEF_IPUT(3, Instruction::IPUT, 46u, 700u, 11u),
1195 DEF_IPUT(3, Instruction::IPUT, 46u, 701u, 10u),
1196 DEF_IGET(4, Instruction::IGET, 50u, 700u, 10u), // Differs from the CONSTs 46u and 53u.
1197 DEF_IGET(4, Instruction::IGET, 51u, 700u, 11u), // Same as 50u.
1198 DEF_IGET(4, Instruction::IGET, 52u, 701u, 10u), // Same as 50u.
1199 DEF_CONST(4, Instruction::CONST, 53u, 3001),
1200 DEF_IPUT(4, Instruction::IPUT, 53u, 700u, 10u),
1201 DEF_IPUT(4, Instruction::IPUT, 53u, 700u, 11u),
1202 DEF_IPUT(4, Instruction::IPUT, 53u, 701u, 10u),
1203 DEF_IGET(5, Instruction::IGET, 57u, 700u, 10u), // Same as the CONST 53u.
1204 DEF_IGET(5, Instruction::IGET, 58u, 700u, 11u), // Same as the CONST 53u.
1205 DEF_IGET(5, Instruction::IGET, 59u, 701u, 10u), // Same as the CONST 53u.
1206 };
1207
1208 PrepareIFields(ifields);
1209 PrepareMIRs(mirs);
1210 PerformGVN();
1211 ASSERT_EQ(arraysize(mirs), value_names_.size());
1212 EXPECT_EQ(value_names_[1], value_names_[2]);
1213 EXPECT_EQ(value_names_[1], value_names_[3]);
1214
1215 EXPECT_NE(value_names_[5], value_names_[6]);
1216 EXPECT_NE(value_names_[5], value_names_[7]);
1217 EXPECT_NE(value_names_[6], value_names_[7]);
1218
1219 EXPECT_NE(value_names_[10], value_names_[12]);
1220 EXPECT_EQ(value_names_[12], value_names_[13]);
1221
1222 EXPECT_NE(value_names_[20], value_names_[16]);
1223 EXPECT_NE(value_names_[20], value_names_[23]);
1224 EXPECT_EQ(value_names_[20], value_names_[21]);
1225 EXPECT_EQ(value_names_[20], value_names_[22]);
1226 EXPECT_NE(value_names_[27], value_names_[16]);
1227 EXPECT_NE(value_names_[27], value_names_[20]);
1228 EXPECT_EQ(value_names_[27], value_names_[28]);
1229 EXPECT_EQ(value_names_[27], value_names_[29]);
1230
1231 EXPECT_NE(value_names_[31], value_names_[34]);
1232 EXPECT_EQ(value_names_[32], value_names_[35]);
1233
1234 EXPECT_EQ(value_names_[39], value_names_[42]);
1235 EXPECT_EQ(value_names_[40], value_names_[43]);
1236
1237 EXPECT_NE(value_names_[50], value_names_[46]);
1238 EXPECT_NE(value_names_[50], value_names_[53]);
1239 EXPECT_EQ(value_names_[50], value_names_[51]);
1240 EXPECT_EQ(value_names_[50], value_names_[52]);
1241 EXPECT_EQ(value_names_[57], value_names_[53]);
1242 EXPECT_EQ(value_names_[58], value_names_[53]);
1243 EXPECT_EQ(value_names_[59], value_names_[53]);
1244 }
1245
TEST_F(GlobalValueNumberingTestLoop,AliasingIFieldsSingleObject)1246 TEST_F(GlobalValueNumberingTestLoop, AliasingIFieldsSingleObject) {
1247 static const IFieldDef ifields[] = {
1248 { 0u, 1u, 0u, false, kDexMemAccessWord },
1249 { 1u, 1u, 1u, false, kDexMemAccessWord },
1250 { 2u, 1u, 2u, false, kDexMemAccessWord },
1251 { 3u, 1u, 3u, false, kDexMemAccessWord },
1252 { 4u, 1u, 4u, false, kDexMemAccessWord },
1253 { 5u, 1u, 5u, false, kDexMemAccessShort },
1254 { 6u, 1u, 6u, false, kDexMemAccessChar },
1255 { 7u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
1256 };
1257 static const MIRDef mirs[] = {
1258 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
1259 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u),
1260 DEF_IGET(4, Instruction::IGET, 1u, 100u, 0u), // Same as at the top.
1261 DEF_IGET(5, Instruction::IGET, 2u, 100u, 0u), // Same as at the top.
1262
1263 DEF_IGET(3, Instruction::IGET, 3u, 100u, 1u),
1264 DEF_IGET(4, Instruction::IGET, 4u, 100u, 1u), // Differs from top...
1265 DEF_IPUT(4, Instruction::IPUT, 5u, 100u, 1u), // Because of this IPUT.
1266 DEF_IGET(5, Instruction::IGET, 6u, 100u, 1u), // Differs from top and the loop IGET.
1267
1268 DEF_IGET(3, Instruction::IGET, 7u, 100u, 2u),
1269 DEF_IPUT(4, Instruction::IPUT, 8u, 100u, 2u), // Because of this IPUT...
1270 DEF_IGET(4, Instruction::IGET, 9u, 100u, 2u), // Differs from top.
1271 DEF_IGET(5, Instruction::IGET, 10u, 100u, 2u), // Differs from top but same as the loop IGET.
1272
1273 DEF_CONST(3, Instruction::CONST, 11u, 3000),
1274 DEF_IPUT(3, Instruction::IPUT, 11u, 100u, 3u),
1275 DEF_IPUT(3, Instruction::IPUT, 11u, 100u, 4u),
1276 DEF_IGET(4, Instruction::IGET, 14u, 100u, 3u), // Differs from 11u and 16u.
1277 DEF_IGET(4, Instruction::IGET, 15u, 100u, 4u), // Same as 14u.
1278 DEF_CONST(4, Instruction::CONST, 16u, 4000),
1279 DEF_IPUT(4, Instruction::IPUT, 16u, 100u, 3u),
1280 DEF_IPUT(4, Instruction::IPUT, 16u, 100u, 4u),
1281 DEF_IGET(5, Instruction::IGET, 19u, 100u, 3u), // Differs from 11u and 14u...
1282 DEF_IGET(5, Instruction::IGET, 20u, 100u, 4u), // and same as the CONST 16u.
1283
1284 DEF_IGET(3, Instruction::IGET_SHORT, 21u, 100u, 5u),
1285 DEF_IGET(3, Instruction::IGET_CHAR, 22u, 100u, 6u),
1286 DEF_IPUT(4, Instruction::IPUT_SHORT, 23u, 100u, 7u), // Clobbers field #5, not #6.
1287 DEF_IGET(5, Instruction::IGET_SHORT, 24u, 100u, 5u), // Differs from the top.
1288 DEF_IGET(5, Instruction::IGET_CHAR, 25u, 100u, 6u), // Same as the top.
1289 };
1290
1291 PrepareIFields(ifields);
1292 PrepareMIRs(mirs);
1293 PerformGVN();
1294 ASSERT_EQ(arraysize(mirs), value_names_.size());
1295 EXPECT_EQ(value_names_[0], value_names_[1]);
1296 EXPECT_EQ(value_names_[0], value_names_[2]);
1297
1298 EXPECT_NE(value_names_[3], value_names_[4]);
1299 EXPECT_NE(value_names_[3], value_names_[6]);
1300 EXPECT_NE(value_names_[4], value_names_[6]);
1301
1302 EXPECT_NE(value_names_[7], value_names_[9]);
1303 EXPECT_EQ(value_names_[9], value_names_[10]);
1304
1305 EXPECT_NE(value_names_[14], value_names_[11]);
1306 EXPECT_NE(value_names_[14], value_names_[16]);
1307 EXPECT_EQ(value_names_[14], value_names_[15]);
1308 EXPECT_NE(value_names_[19], value_names_[11]);
1309 EXPECT_NE(value_names_[19], value_names_[14]);
1310 EXPECT_EQ(value_names_[19], value_names_[16]);
1311 EXPECT_EQ(value_names_[19], value_names_[20]);
1312
1313 EXPECT_NE(value_names_[21], value_names_[24]);
1314 EXPECT_EQ(value_names_[22], value_names_[25]);
1315 }
1316
TEST_F(GlobalValueNumberingTestLoop,AliasingIFieldsTwoObjects)1317 TEST_F(GlobalValueNumberingTestLoop, AliasingIFieldsTwoObjects) {
1318 static const IFieldDef ifields[] = {
1319 { 0u, 1u, 0u, false, kDexMemAccessWord },
1320 { 1u, 1u, 1u, false, kDexMemAccessWord },
1321 { 2u, 1u, 2u, false, kDexMemAccessWord },
1322 { 3u, 1u, 3u, false, kDexMemAccessShort },
1323 { 4u, 1u, 4u, false, kDexMemAccessChar },
1324 { 5u, 0u, 0u, false, kDexMemAccessShort }, // Unresolved.
1325 { 6u, 1u, 6u, false, kDexMemAccessWord },
1326 { 7u, 1u, 7u, false, kDexMemAccessWord },
1327 };
1328 static const MIRDef mirs[] = {
1329 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
1330 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u),
1331 DEF_IPUT(4, Instruction::IPUT, 1u, 101u, 0u), // May alias with the IGET at the top.
1332 DEF_IGET(5, Instruction::IGET, 2u, 100u, 0u), // Differs from the top.
1333
1334 DEF_IGET(3, Instruction::IGET, 3u, 100u, 1u),
1335 DEF_IPUT(4, Instruction::IPUT, 3u, 101u, 1u), // If aliasing, stores the same value.
1336 DEF_IGET(5, Instruction::IGET, 5u, 100u, 1u), // Same as the top.
1337
1338 DEF_IGET(3, Instruction::IGET, 6u, 100u, 2u),
1339 DEF_CONST(4, Instruction::CONST, 7u, 1000),
1340 DEF_IPUT(4, Instruction::IPUT, 7u, 101u, 2u),
1341 DEF_IGET(5, Instruction::IGET, 9u, 100u, 2u), // Differs from the top and the CONST.
1342
1343 DEF_IGET(3, Instruction::IGET_SHORT, 10u, 100u, 3u),
1344 DEF_IGET(3, Instruction::IGET_CHAR, 11u, 100u, 4u),
1345 DEF_IPUT(4, Instruction::IPUT_SHORT, 12u, 101u, 5u), // Clobbers field #3, not #4.
1346 DEF_IGET(5, Instruction::IGET_SHORT, 13u, 100u, 3u), // Differs from the top.
1347 DEF_IGET(5, Instruction::IGET_CHAR, 14u, 100u, 4u), // Same as the top.
1348
1349 DEF_CONST(3, Instruction::CONST, 15u, 3000),
1350 DEF_IPUT(3, Instruction::IPUT, 15u, 100u, 6u),
1351 DEF_IPUT(3, Instruction::IPUT, 15u, 100u, 7u),
1352 DEF_IPUT(3, Instruction::IPUT, 15u, 101u, 6u),
1353 DEF_IGET(4, Instruction::IGET, 19u, 100u, 6u), // Differs from CONSTs 15u and 22u.
1354 DEF_IGET(4, Instruction::IGET, 20u, 100u, 7u), // Same value as 19u.
1355 DEF_IGET(4, Instruction::IGET, 21u, 101u, 6u), // Same value as read from field #7.
1356 DEF_CONST(4, Instruction::CONST, 22u, 3001),
1357 DEF_IPUT(4, Instruction::IPUT, 22u, 100u, 6u),
1358 DEF_IPUT(4, Instruction::IPUT, 22u, 100u, 7u),
1359 DEF_IPUT(4, Instruction::IPUT, 22u, 101u, 6u),
1360 DEF_IGET(5, Instruction::IGET, 26u, 100u, 6u), // Same as CONST 22u.
1361 DEF_IGET(5, Instruction::IGET, 27u, 100u, 7u), // Same as CONST 22u.
1362 DEF_IGET(5, Instruction::IGET, 28u, 101u, 6u), // Same as CONST 22u.
1363 };
1364
1365 PrepareIFields(ifields);
1366 PrepareMIRs(mirs);
1367 PerformGVN();
1368 ASSERT_EQ(arraysize(mirs), value_names_.size());
1369 EXPECT_NE(value_names_[0], value_names_[2]);
1370
1371 EXPECT_EQ(value_names_[3], value_names_[5]);
1372
1373 EXPECT_NE(value_names_[6], value_names_[9]);
1374 EXPECT_NE(value_names_[7], value_names_[9]);
1375
1376 EXPECT_NE(value_names_[10], value_names_[13]);
1377 EXPECT_EQ(value_names_[11], value_names_[14]);
1378
1379 EXPECT_NE(value_names_[19], value_names_[15]);
1380 EXPECT_NE(value_names_[19], value_names_[22]);
1381 EXPECT_EQ(value_names_[22], value_names_[26]);
1382 EXPECT_EQ(value_names_[22], value_names_[27]);
1383 EXPECT_EQ(value_names_[22], value_names_[28]);
1384 }
1385
TEST_F(GlobalValueNumberingTestLoop,IFieldToBaseDependency)1386 TEST_F(GlobalValueNumberingTestLoop, IFieldToBaseDependency) {
1387 static const IFieldDef ifields[] = {
1388 { 0u, 1u, 0u, false, kDexMemAccessWord },
1389 };
1390 static const MIRDef mirs[] = {
1391 // For the IGET that loads sreg 3u using base 2u, the following IPUT creates a dependency
1392 // from the field value to the base. However, this dependency does not result in an
1393 // infinite loop since the merge of the field value for base 0u gets assigned a value name
1394 // based only on the base 0u, not on the actual value, and breaks the dependency cycle.
1395 DEF_IGET(3, Instruction::IGET, 0u, 100u, 0u),
1396 DEF_IGET(3, Instruction::IGET, 1u, 0u, 0u),
1397 DEF_IGET(4, Instruction::IGET, 2u, 0u, 0u),
1398 DEF_IGET(4, Instruction::IGET, 3u, 2u, 0u),
1399 DEF_IPUT(4, Instruction::IPUT, 3u, 0u, 0u),
1400 DEF_IGET(5, Instruction::IGET, 5u, 0u, 0u),
1401 };
1402
1403 PrepareIFields(ifields);
1404 PrepareMIRs(mirs);
1405 PerformGVN();
1406 ASSERT_EQ(arraysize(mirs), value_names_.size());
1407 EXPECT_NE(value_names_[1], value_names_[2]);
1408 EXPECT_EQ(value_names_[3], value_names_[5]);
1409 }
1410
TEST_F(GlobalValueNumberingTestLoop,SFields)1411 TEST_F(GlobalValueNumberingTestLoop, SFields) {
1412 static const SFieldDef sfields[] = {
1413 { 0u, 1u, 0u, false, kDexMemAccessWord },
1414 { 1u, 1u, 1u, false, kDexMemAccessWord },
1415 { 2u, 1u, 2u, false, kDexMemAccessWord },
1416 };
1417 static const MIRDef mirs[] = {
1418 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
1419 DEF_SGET(3, Instruction::SGET, 0u, 0u),
1420 DEF_SGET(4, Instruction::SGET, 1u, 0u), // Same as at the top.
1421 DEF_SGET(5, Instruction::SGET, 2u, 0u), // Same as at the top.
1422
1423 DEF_SGET(3, Instruction::SGET, 3u, 1u),
1424 DEF_SGET(4, Instruction::SGET, 4u, 1u), // Differs from top...
1425 DEF_SPUT(4, Instruction::SPUT, 5u, 1u), // Because of this SPUT.
1426 DEF_SGET(5, Instruction::SGET, 6u, 1u), // Differs from top and the loop SGET.
1427
1428 DEF_SGET(3, Instruction::SGET, 7u, 2u),
1429 DEF_SPUT(4, Instruction::SPUT, 8u, 2u), // Because of this SPUT...
1430 DEF_SGET(4, Instruction::SGET, 9u, 2u), // Differs from top.
1431 DEF_SGET(5, Instruction::SGET, 10u, 2u), // Differs from top but same as the loop SGET.
1432 };
1433
1434 PrepareSFields(sfields);
1435 PrepareMIRs(mirs);
1436 PerformGVN();
1437 ASSERT_EQ(arraysize(mirs), value_names_.size());
1438 EXPECT_EQ(value_names_[0], value_names_[1]);
1439 EXPECT_EQ(value_names_[0], value_names_[2]);
1440
1441 EXPECT_NE(value_names_[3], value_names_[4]);
1442 EXPECT_NE(value_names_[3], value_names_[6]);
1443 EXPECT_NE(value_names_[4], value_names_[5]);
1444
1445 EXPECT_NE(value_names_[7], value_names_[9]);
1446 EXPECT_EQ(value_names_[9], value_names_[10]);
1447 }
1448
TEST_F(GlobalValueNumberingTestLoop,NonAliasingArrays)1449 TEST_F(GlobalValueNumberingTestLoop, NonAliasingArrays) {
1450 static const MIRDef mirs[] = {
1451 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
1452 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 100u),
1453 DEF_AGET(3, Instruction::AGET, 1u, 100u, 101u),
1454 DEF_AGET(4, Instruction::AGET, 2u, 100u, 101u), // Same as at the top.
1455 DEF_AGET(5, Instruction::AGET, 3u, 100u, 101u), // Same as at the top.
1456
1457 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u),
1458 DEF_AGET(3, Instruction::AGET, 5u, 200u, 201u),
1459 DEF_AGET(4, Instruction::AGET, 6u, 200u, 201u), // Differs from top...
1460 DEF_APUT(4, Instruction::APUT, 7u, 200u, 201u), // Because of this IPUT.
1461 DEF_AGET(5, Instruction::AGET, 8u, 200u, 201u), // Differs from top and the loop AGET.
1462
1463 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 300u),
1464 DEF_AGET(3, Instruction::AGET, 10u, 300u, 301u),
1465 DEF_APUT(4, Instruction::APUT, 11u, 300u, 301u), // Because of this IPUT...
1466 DEF_AGET(4, Instruction::AGET, 12u, 300u, 301u), // Differs from top.
1467 DEF_AGET(5, Instruction::AGET, 13u, 300u, 301u), // Differs from top but == the loop AGET.
1468
1469 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 400u),
1470 DEF_CONST(3, Instruction::CONST, 15u, 3000),
1471 DEF_APUT(3, Instruction::APUT, 15u, 400u, 401u),
1472 DEF_APUT(3, Instruction::APUT, 15u, 400u, 402u),
1473 DEF_AGET(4, Instruction::AGET, 18u, 400u, 401u), // Differs from 15u and 20u.
1474 DEF_AGET(4, Instruction::AGET, 19u, 400u, 402u), // Same as 18u.
1475 DEF_CONST(4, Instruction::CONST, 20u, 4000),
1476 DEF_APUT(4, Instruction::APUT, 20u, 400u, 401u),
1477 DEF_APUT(4, Instruction::APUT, 20u, 400u, 402u),
1478 DEF_AGET(5, Instruction::AGET, 23u, 400u, 401u), // Differs from 15u and 18u...
1479 DEF_AGET(5, Instruction::AGET, 24u, 400u, 402u), // and same as the CONST 20u.
1480
1481 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 500u),
1482 DEF_AGET(3, Instruction::AGET, 26u, 500u, 501u),
1483 DEF_APUT(4, Instruction::APUT, 27u, 500u, 502u), // Clobbers element at index 501u.
1484 DEF_AGET(5, Instruction::AGET, 28u, 500u, 501u), // Differs from the top.
1485 };
1486
1487 PrepareMIRs(mirs);
1488 PerformGVN();
1489 ASSERT_EQ(arraysize(mirs), value_names_.size());
1490 EXPECT_EQ(value_names_[1], value_names_[2]);
1491 EXPECT_EQ(value_names_[1], value_names_[3]);
1492
1493 EXPECT_NE(value_names_[5], value_names_[6]);
1494 EXPECT_NE(value_names_[5], value_names_[8]);
1495 EXPECT_NE(value_names_[6], value_names_[8]);
1496
1497 EXPECT_NE(value_names_[10], value_names_[12]);
1498 EXPECT_EQ(value_names_[12], value_names_[13]);
1499
1500 EXPECT_NE(value_names_[18], value_names_[15]);
1501 EXPECT_NE(value_names_[18], value_names_[20]);
1502 EXPECT_EQ(value_names_[18], value_names_[19]);
1503 EXPECT_NE(value_names_[23], value_names_[15]);
1504 EXPECT_NE(value_names_[23], value_names_[18]);
1505 EXPECT_EQ(value_names_[23], value_names_[20]);
1506 EXPECT_EQ(value_names_[23], value_names_[24]);
1507
1508 EXPECT_NE(value_names_[26], value_names_[28]);
1509 }
1510
TEST_F(GlobalValueNumberingTestLoop,AliasingArrays)1511 TEST_F(GlobalValueNumberingTestLoop, AliasingArrays) {
1512 static const MIRDef mirs[] = {
1513 // NOTE: MIRs here are ordered by unique tests. They will be put into appropriate blocks.
1514 DEF_AGET(3, Instruction::AGET_WIDE, 0u, 100u, 101u),
1515 DEF_AGET(4, Instruction::AGET_WIDE, 2u, 100u, 101u), // Same as at the top.
1516 DEF_AGET(5, Instruction::AGET_WIDE, 4u, 100u, 101u), // Same as at the top.
1517
1518 DEF_AGET(3, Instruction::AGET_BYTE, 6u, 200u, 201u),
1519 DEF_AGET(4, Instruction::AGET_BYTE, 7u, 200u, 201u), // Differs from top...
1520 DEF_APUT(4, Instruction::APUT_BYTE, 8u, 200u, 201u), // Because of this IPUT.
1521 DEF_AGET(5, Instruction::AGET_BYTE, 9u, 200u, 201u), // Differs from top and the loop AGET.
1522
1523 DEF_AGET(3, Instruction::AGET, 10u, 300u, 301u),
1524 DEF_APUT(4, Instruction::APUT, 11u, 300u, 301u), // Because of this IPUT...
1525 DEF_AGET(4, Instruction::AGET, 12u, 300u, 301u), // Differs from top.
1526 DEF_AGET(5, Instruction::AGET, 13u, 300u, 301u), // Differs from top but == the loop AGET.
1527
1528 DEF_CONST(3, Instruction::CONST, 14u, 3000),
1529 DEF_APUT(3, Instruction::APUT_CHAR, 14u, 400u, 401u),
1530 DEF_APUT(3, Instruction::APUT_CHAR, 14u, 400u, 402u),
1531 DEF_AGET(4, Instruction::AGET_CHAR, 15u, 400u, 401u), // Differs from 11u and 16u.
1532 DEF_AGET(4, Instruction::AGET_CHAR, 16u, 400u, 402u), // Same as 14u.
1533 DEF_CONST(4, Instruction::CONST, 17u, 4000),
1534 DEF_APUT(4, Instruction::APUT_CHAR, 17u, 400u, 401u),
1535 DEF_APUT(4, Instruction::APUT_CHAR, 17u, 400u, 402u),
1536 DEF_AGET(5, Instruction::AGET_CHAR, 19u, 400u, 401u), // Differs from 11u and 14u...
1537 DEF_AGET(5, Instruction::AGET_CHAR, 20u, 400u, 402u), // and same as the CONST 16u.
1538
1539 DEF_AGET(3, Instruction::AGET_SHORT, 21u, 500u, 501u),
1540 DEF_APUT(4, Instruction::APUT_SHORT, 22u, 500u, 502u), // Clobbers element at index 501u.
1541 DEF_AGET(5, Instruction::AGET_SHORT, 23u, 500u, 501u), // Differs from the top.
1542
1543 DEF_AGET(3, Instruction::AGET_OBJECT, 24u, 600u, 601u),
1544 DEF_APUT(4, Instruction::APUT_OBJECT, 25u, 601u, 602u), // Clobbers 600u/601u.
1545 DEF_AGET(5, Instruction::AGET_OBJECT, 26u, 600u, 601u), // Differs from the top.
1546
1547 DEF_AGET(3, Instruction::AGET_BOOLEAN, 27u, 700u, 701u),
1548 DEF_APUT(4, Instruction::APUT_BOOLEAN, 27u, 701u, 702u), // Storing the same value.
1549 DEF_AGET(5, Instruction::AGET_BOOLEAN, 29u, 700u, 701u), // Differs from the top.
1550 };
1551
1552 PrepareMIRs(mirs);
1553 static const int32_t wide_sregs[] = { 0, 2, 4 };
1554 MarkAsWideSRegs(wide_sregs);
1555 PerformGVN();
1556 ASSERT_EQ(arraysize(mirs), value_names_.size());
1557 EXPECT_EQ(value_names_[0], value_names_[1]);
1558 EXPECT_EQ(value_names_[0], value_names_[2]);
1559
1560 EXPECT_NE(value_names_[3], value_names_[4]);
1561 EXPECT_NE(value_names_[3], value_names_[6]);
1562 EXPECT_NE(value_names_[4], value_names_[6]);
1563
1564 EXPECT_NE(value_names_[7], value_names_[9]);
1565 EXPECT_EQ(value_names_[9], value_names_[10]);
1566
1567 EXPECT_NE(value_names_[14], value_names_[11]);
1568 EXPECT_NE(value_names_[14], value_names_[16]);
1569 EXPECT_EQ(value_names_[14], value_names_[15]);
1570 EXPECT_NE(value_names_[19], value_names_[11]);
1571 EXPECT_NE(value_names_[19], value_names_[14]);
1572 EXPECT_EQ(value_names_[19], value_names_[16]);
1573 EXPECT_EQ(value_names_[19], value_names_[20]);
1574
1575 EXPECT_NE(value_names_[21], value_names_[23]);
1576
1577 EXPECT_NE(value_names_[24], value_names_[26]);
1578
1579 EXPECT_EQ(value_names_[27], value_names_[29]);
1580 }
1581
TEST_F(GlobalValueNumberingTestLoop,Phi)1582 TEST_F(GlobalValueNumberingTestLoop, Phi) {
1583 static const MIRDef mirs[] = {
1584 DEF_CONST(3, Instruction::CONST, 0u, 1000),
1585 DEF_PHI2(4, 1u, 0u, 6u), // Merge CONST 0u (1000) with the same.
1586 DEF_PHI2(4, 2u, 0u, 7u), // Merge CONST 0u (1000) with the Phi itself.
1587 DEF_PHI2(4, 3u, 0u, 8u), // Merge CONST 0u (1000) and CONST 4u (2000).
1588 DEF_PHI2(4, 4u, 0u, 9u), // Merge CONST 0u (1000) and Phi 3u.
1589 DEF_CONST(4, Instruction::CONST, 5u, 2000),
1590 DEF_MOVE(4, Instruction::MOVE, 6u, 0u),
1591 DEF_MOVE(4, Instruction::MOVE, 7u, 2u),
1592 DEF_MOVE(4, Instruction::MOVE, 8u, 5u),
1593 DEF_MOVE(4, Instruction::MOVE, 9u, 3u),
1594 };
1595
1596 PrepareMIRs(mirs);
1597 PerformGVN();
1598 ASSERT_EQ(arraysize(mirs), value_names_.size());
1599 EXPECT_EQ(value_names_[1], value_names_[0]);
1600 EXPECT_EQ(value_names_[2], value_names_[0]);
1601
1602 EXPECT_NE(value_names_[3], value_names_[0]);
1603 EXPECT_NE(value_names_[3], value_names_[5]);
1604 EXPECT_NE(value_names_[4], value_names_[0]);
1605 EXPECT_NE(value_names_[4], value_names_[5]);
1606 EXPECT_NE(value_names_[4], value_names_[3]);
1607 }
1608
TEST_F(GlobalValueNumberingTestLoop,IFieldLoopVariable)1609 TEST_F(GlobalValueNumberingTestLoop, IFieldLoopVariable) {
1610 static const IFieldDef ifields[] = {
1611 { 0u, 1u, 0u, false, kDexMemAccessWord },
1612 };
1613 static const MIRDef mirs[] = {
1614 DEF_CONST(3, Instruction::CONST, 0u, 0),
1615 DEF_IPUT(3, Instruction::IPUT, 0u, 100u, 0u),
1616 DEF_IGET(4, Instruction::IGET, 2u, 100u, 0u),
1617 DEF_BINOP(4, Instruction::ADD_INT, 3u, 2u, 101u),
1618 DEF_IPUT(4, Instruction::IPUT, 3u, 100u, 0u),
1619 };
1620
1621 PrepareIFields(ifields);
1622 PrepareMIRs(mirs);
1623 PerformGVN();
1624 ASSERT_EQ(arraysize(mirs), value_names_.size());
1625 EXPECT_NE(value_names_[2], value_names_[0]);
1626 EXPECT_NE(value_names_[3], value_names_[0]);
1627 EXPECT_NE(value_names_[3], value_names_[2]);
1628
1629
1630 // Set up vreg_to_ssa_map_exit for prologue and loop and set post-processing mode
1631 // as needed for GetStartingVregValueNumber().
1632 const int32_t prologue_vreg_to_ssa_map_exit[] = { 0 };
1633 const int32_t loop_vreg_to_ssa_map_exit[] = { 3 };
1634 PrepareVregToSsaMapExit(3, prologue_vreg_to_ssa_map_exit);
1635 PrepareVregToSsaMapExit(4, loop_vreg_to_ssa_map_exit);
1636 gvn_->StartPostProcessing();
1637
1638 // Check that vreg 0 has the same value number as the result of IGET 2u.
1639 const LocalValueNumbering* loop = gvn_->GetLvn(4);
1640 EXPECT_EQ(value_names_[2], loop->GetStartingVregValueNumber(0));
1641 }
1642
TEST_F(GlobalValueNumberingTestCatch,IFields)1643 TEST_F(GlobalValueNumberingTestCatch, IFields) {
1644 static const IFieldDef ifields[] = {
1645 { 0u, 1u, 0u, false, kDexMemAccessWord },
1646 { 1u, 1u, 1u, false, kDexMemAccessWord },
1647 };
1648 static const MIRDef mirs[] = {
1649 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 200u),
1650 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 201u),
1651 DEF_IGET(3, Instruction::IGET, 2u, 100u, 0u),
1652 DEF_IGET(3, Instruction::IGET, 3u, 200u, 0u),
1653 DEF_IGET(3, Instruction::IGET, 4u, 201u, 0u),
1654 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 201u), // Clobbering catch, 201u escapes.
1655 DEF_IGET(4, Instruction::IGET, 6u, 100u, 0u), // Differs from IGET 2u.
1656 DEF_IPUT(4, Instruction::IPUT, 6u, 100u, 1u),
1657 DEF_IPUT(4, Instruction::IPUT, 6u, 101u, 0u),
1658 DEF_IPUT(4, Instruction::IPUT, 6u, 200u, 0u),
1659 DEF_IGET(5, Instruction::IGET, 10u, 100u, 0u), // Differs from IGETs 2u and 6u.
1660 DEF_IGET(5, Instruction::IGET, 11u, 200u, 0u), // Same as the top.
1661 DEF_IGET(5, Instruction::IGET, 12u, 201u, 0u), // Differs from the top, 201u escaped.
1662 DEF_IPUT(5, Instruction::IPUT, 10u, 100u, 1u),
1663 DEF_IPUT(5, Instruction::IPUT, 10u, 101u, 0u),
1664 DEF_IPUT(5, Instruction::IPUT, 10u, 200u, 0u),
1665 DEF_IGET(6, Instruction::IGET, 16u, 100u, 0u), // Differs from IGETs 2u, 6u and 10u.
1666 DEF_IGET(6, Instruction::IGET, 17u, 100u, 1u), // Same as IGET 16u.
1667 DEF_IGET(6, Instruction::IGET, 18u, 101u, 0u), // Same as IGET 16u.
1668 DEF_IGET(6, Instruction::IGET, 19u, 200u, 0u), // Same as IGET 16u.
1669 };
1670
1671 PrepareIFields(ifields);
1672 PrepareMIRs(mirs);
1673 PerformGVN();
1674 ASSERT_EQ(arraysize(mirs), value_names_.size());
1675 EXPECT_NE(value_names_[2], value_names_[6]);
1676 EXPECT_NE(value_names_[2], value_names_[10]);
1677 EXPECT_NE(value_names_[6], value_names_[10]);
1678 EXPECT_EQ(value_names_[3], value_names_[11]);
1679 EXPECT_NE(value_names_[4], value_names_[12]);
1680
1681 EXPECT_NE(value_names_[2], value_names_[16]);
1682 EXPECT_NE(value_names_[6], value_names_[16]);
1683 EXPECT_NE(value_names_[10], value_names_[16]);
1684 EXPECT_EQ(value_names_[16], value_names_[17]);
1685 EXPECT_EQ(value_names_[16], value_names_[18]);
1686 EXPECT_EQ(value_names_[16], value_names_[19]);
1687 }
1688
TEST_F(GlobalValueNumberingTestCatch,SFields)1689 TEST_F(GlobalValueNumberingTestCatch, SFields) {
1690 static const SFieldDef sfields[] = {
1691 { 0u, 1u, 0u, false, kDexMemAccessWord },
1692 { 1u, 1u, 1u, false, kDexMemAccessWord },
1693 };
1694 static const MIRDef mirs[] = {
1695 DEF_SGET(3, Instruction::SGET, 0u, 0u),
1696 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 100u), // Clobbering catch.
1697 DEF_SGET(4, Instruction::SGET, 2u, 0u), // Differs from SGET 0u.
1698 DEF_SPUT(4, Instruction::SPUT, 2u, 1u),
1699 DEF_SGET(5, Instruction::SGET, 4u, 0u), // Differs from SGETs 0u and 2u.
1700 DEF_SPUT(5, Instruction::SPUT, 4u, 1u),
1701 DEF_SGET(6, Instruction::SGET, 6u, 0u), // Differs from SGETs 0u, 2u and 4u.
1702 DEF_SGET(6, Instruction::SGET, 7u, 1u), // Same as field #1.
1703 };
1704
1705 PrepareSFields(sfields);
1706 PrepareMIRs(mirs);
1707 PerformGVN();
1708 ASSERT_EQ(arraysize(mirs), value_names_.size());
1709 EXPECT_NE(value_names_[0], value_names_[2]);
1710 EXPECT_NE(value_names_[0], value_names_[4]);
1711 EXPECT_NE(value_names_[2], value_names_[4]);
1712 EXPECT_NE(value_names_[0], value_names_[6]);
1713 EXPECT_NE(value_names_[2], value_names_[6]);
1714 EXPECT_NE(value_names_[4], value_names_[6]);
1715 EXPECT_EQ(value_names_[6], value_names_[7]);
1716 }
1717
TEST_F(GlobalValueNumberingTestCatch,Arrays)1718 TEST_F(GlobalValueNumberingTestCatch, Arrays) {
1719 static const MIRDef mirs[] = {
1720 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u),
1721 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 201u),
1722 DEF_AGET(3, Instruction::AGET, 2u, 100u, 101u),
1723 DEF_AGET(3, Instruction::AGET, 3u, 200u, 202u),
1724 DEF_AGET(3, Instruction::AGET, 4u, 200u, 203u),
1725 DEF_AGET(3, Instruction::AGET, 5u, 201u, 202u),
1726 DEF_AGET(3, Instruction::AGET, 6u, 201u, 203u),
1727 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 201u), // Clobbering catch, 201u escapes.
1728 DEF_AGET(4, Instruction::AGET, 8u, 100u, 101u), // Differs from AGET 2u.
1729 DEF_APUT(4, Instruction::APUT, 8u, 100u, 102u),
1730 DEF_APUT(4, Instruction::APUT, 8u, 200u, 202u),
1731 DEF_APUT(4, Instruction::APUT, 8u, 200u, 203u),
1732 DEF_APUT(4, Instruction::APUT, 8u, 201u, 202u),
1733 DEF_APUT(4, Instruction::APUT, 8u, 201u, 203u),
1734 DEF_AGET(5, Instruction::AGET, 14u, 100u, 101u), // Differs from AGETs 2u and 8u.
1735 DEF_AGET(5, Instruction::AGET, 15u, 200u, 202u), // Same as AGET 3u.
1736 DEF_AGET(5, Instruction::AGET, 16u, 200u, 203u), // Same as AGET 4u.
1737 DEF_AGET(5, Instruction::AGET, 17u, 201u, 202u), // Differs from AGET 5u.
1738 DEF_AGET(5, Instruction::AGET, 18u, 201u, 203u), // Differs from AGET 6u.
1739 DEF_APUT(5, Instruction::APUT, 14u, 100u, 102u),
1740 DEF_APUT(5, Instruction::APUT, 14u, 200u, 202u),
1741 DEF_APUT(5, Instruction::APUT, 14u, 200u, 203u),
1742 DEF_APUT(5, Instruction::APUT, 14u, 201u, 202u),
1743 DEF_APUT(5, Instruction::APUT, 14u, 201u, 203u),
1744 DEF_AGET(6, Instruction::AGET, 24u, 100u, 101u), // Differs from AGETs 2u, 8u and 14u.
1745 DEF_AGET(6, Instruction::AGET, 25u, 100u, 101u), // Same as AGET 24u.
1746 DEF_AGET(6, Instruction::AGET, 26u, 200u, 202u), // Same as AGET 24u.
1747 DEF_AGET(6, Instruction::AGET, 27u, 200u, 203u), // Same as AGET 24u.
1748 DEF_AGET(6, Instruction::AGET, 28u, 201u, 202u), // Same as AGET 24u.
1749 DEF_AGET(6, Instruction::AGET, 29u, 201u, 203u), // Same as AGET 24u.
1750 };
1751
1752 PrepareMIRs(mirs);
1753 PerformGVN();
1754 ASSERT_EQ(arraysize(mirs), value_names_.size());
1755 EXPECT_NE(value_names_[2], value_names_[8]);
1756 EXPECT_NE(value_names_[2], value_names_[14]);
1757 EXPECT_NE(value_names_[8], value_names_[14]);
1758 EXPECT_EQ(value_names_[3], value_names_[15]);
1759 EXPECT_EQ(value_names_[4], value_names_[16]);
1760 EXPECT_NE(value_names_[5], value_names_[17]);
1761 EXPECT_NE(value_names_[6], value_names_[18]);
1762 EXPECT_NE(value_names_[2], value_names_[24]);
1763 EXPECT_NE(value_names_[8], value_names_[24]);
1764 EXPECT_NE(value_names_[14], value_names_[24]);
1765 EXPECT_EQ(value_names_[24], value_names_[25]);
1766 EXPECT_EQ(value_names_[24], value_names_[26]);
1767 EXPECT_EQ(value_names_[24], value_names_[27]);
1768 EXPECT_EQ(value_names_[24], value_names_[28]);
1769 EXPECT_EQ(value_names_[24], value_names_[29]);
1770 }
1771
TEST_F(GlobalValueNumberingTestCatch,Phi)1772 TEST_F(GlobalValueNumberingTestCatch, Phi) {
1773 static const MIRDef mirs[] = {
1774 DEF_CONST(3, Instruction::CONST, 0u, 1000),
1775 DEF_CONST(3, Instruction::CONST, 1u, 2000),
1776 DEF_MOVE(3, Instruction::MOVE, 2u, 1u),
1777 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 100u), // Clobbering catch.
1778 DEF_CONST(5, Instruction::CONST, 4u, 1000),
1779 DEF_CONST(5, Instruction::CONST, 5u, 3000),
1780 DEF_MOVE(5, Instruction::MOVE, 6u, 5u),
1781 DEF_PHI2(6, 7u, 0u, 4u),
1782 DEF_PHI2(6, 8u, 0u, 5u),
1783 DEF_PHI2(6, 9u, 0u, 6u),
1784 DEF_PHI2(6, 10u, 1u, 4u),
1785 DEF_PHI2(6, 11u, 1u, 5u),
1786 DEF_PHI2(6, 12u, 1u, 6u),
1787 DEF_PHI2(6, 13u, 2u, 4u),
1788 DEF_PHI2(6, 14u, 2u, 5u),
1789 DEF_PHI2(6, 15u, 2u, 6u),
1790 };
1791 PrepareMIRs(mirs);
1792 PerformGVN();
1793 ASSERT_EQ(arraysize(mirs), value_names_.size());
1794 ASSERT_EQ(value_names_[4], value_names_[0]); // Both CONSTs are 1000.
1795 EXPECT_EQ(value_names_[7], value_names_[0]); // Merging CONST 0u and CONST 4u, both 1000.
1796 EXPECT_NE(value_names_[8], value_names_[0]);
1797 EXPECT_NE(value_names_[8], value_names_[5]);
1798 EXPECT_EQ(value_names_[9], value_names_[8]);
1799 EXPECT_NE(value_names_[10], value_names_[1]);
1800 EXPECT_NE(value_names_[10], value_names_[4]);
1801 EXPECT_NE(value_names_[10], value_names_[8]);
1802 EXPECT_NE(value_names_[11], value_names_[1]);
1803 EXPECT_NE(value_names_[11], value_names_[5]);
1804 EXPECT_NE(value_names_[11], value_names_[8]);
1805 EXPECT_NE(value_names_[11], value_names_[10]);
1806 EXPECT_EQ(value_names_[12], value_names_[11]);
1807 EXPECT_EQ(value_names_[13], value_names_[10]);
1808 EXPECT_EQ(value_names_[14], value_names_[11]);
1809 EXPECT_EQ(value_names_[15], value_names_[11]);
1810 }
1811
TEST_F(GlobalValueNumberingTest,NullCheckIFields)1812 TEST_F(GlobalValueNumberingTest, NullCheckIFields) {
1813 static const IFieldDef ifields[] = {
1814 { 0u, 1u, 0u, false, kDexMemAccessObject }, // Object.
1815 { 1u, 1u, 1u, false, kDexMemAccessObject }, // Object.
1816 };
1817 static const BBDef bbs[] = {
1818 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
1819 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
1820 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
1821 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // 4 is fall-through, 5 is taken.
1822 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)),
1823 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)),
1824 };
1825 static const MIRDef mirs[] = {
1826 DEF_IGET(3, Instruction::IGET_OBJECT, 0u, 100u, 0u),
1827 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 100u, 1u),
1828 DEF_IGET(3, Instruction::IGET_OBJECT, 2u, 101u, 0u),
1829 DEF_IFZ(3, Instruction::IF_NEZ, 0u), // Null-check for field #0 for taken.
1830 DEF_UNIQUE_REF(4, Instruction::NEW_ARRAY, 4u),
1831 DEF_IPUT(4, Instruction::IPUT_OBJECT, 4u, 100u, 0u),
1832 DEF_IPUT(4, Instruction::IPUT_OBJECT, 4u, 100u, 1u),
1833 DEF_IPUT(4, Instruction::IPUT_OBJECT, 4u, 101u, 0u),
1834 DEF_IGET(5, Instruction::IGET_OBJECT, 8u, 100u, 0u), // 100u/#0, IF_NEZ/NEW_ARRAY.
1835 DEF_IGET(5, Instruction::IGET_OBJECT, 9u, 100u, 1u), // 100u/#1, -/NEW_ARRAY.
1836 DEF_IGET(5, Instruction::IGET_OBJECT, 10u, 101u, 0u), // 101u/#0, -/NEW_ARRAY.
1837 DEF_CONST(5, Instruction::CONST, 11u, 0),
1838 DEF_AGET(5, Instruction::AGET, 12u, 8u, 11u), // Null-check eliminated.
1839 DEF_AGET(5, Instruction::AGET, 13u, 9u, 11u), // Null-check kept.
1840 DEF_AGET(5, Instruction::AGET, 14u, 10u, 11u), // Null-check kept.
1841 };
1842 static const bool expected_ignore_null_check[] = {
1843 false, true, false, false, // BB #3; unimportant.
1844 false, true, true, true, // BB #4; unimportant.
1845 true, true, true, false, true, false, false, // BB #5; only the last three are important.
1846 };
1847
1848 PrepareIFields(ifields);
1849 PrepareBasicBlocks(bbs);
1850 PrepareMIRs(mirs);
1851 PerformGVN();
1852 ASSERT_EQ(arraysize(mirs), value_names_.size());
1853 PerformGVNCodeModifications();
1854 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
1855 for (size_t i = 0u; i != arraysize(mirs); ++i) {
1856 EXPECT_EQ(expected_ignore_null_check[i],
1857 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
1858 }
1859 }
1860
TEST_F(GlobalValueNumberingTest,NullCheckSFields)1861 TEST_F(GlobalValueNumberingTest, NullCheckSFields) {
1862 static const SFieldDef sfields[] = {
1863 { 0u, 1u, 0u, false, kDexMemAccessObject },
1864 { 1u, 1u, 1u, false, kDexMemAccessObject },
1865 };
1866 static const BBDef bbs[] = {
1867 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
1868 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
1869 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
1870 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // 4 is fall-through, 5 is taken.
1871 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)),
1872 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)),
1873 };
1874 static const MIRDef mirs[] = {
1875 DEF_SGET(3, Instruction::SGET_OBJECT, 0u, 0u),
1876 DEF_SGET(3, Instruction::SGET_OBJECT, 1u, 1u),
1877 DEF_IFZ(3, Instruction::IF_NEZ, 0u), // Null-check for field #0 for taken.
1878 DEF_UNIQUE_REF(4, Instruction::NEW_ARRAY, 3u),
1879 DEF_SPUT(4, Instruction::SPUT_OBJECT, 3u, 0u),
1880 DEF_SPUT(4, Instruction::SPUT_OBJECT, 3u, 1u),
1881 DEF_SGET(5, Instruction::SGET_OBJECT, 6u, 0u), // Field #0 is null-checked, IF_NEZ/NEW_ARRAY.
1882 DEF_SGET(5, Instruction::SGET_OBJECT, 7u, 1u), // Field #1 is not null-checked, -/NEW_ARRAY.
1883 DEF_CONST(5, Instruction::CONST, 8u, 0),
1884 DEF_AGET(5, Instruction::AGET, 9u, 6u, 8u), // Null-check eliminated.
1885 DEF_AGET(5, Instruction::AGET, 10u, 7u, 8u), // Null-check kept.
1886 };
1887 static const bool expected_ignore_null_check[] = {
1888 false, false, false, false, false, false, false, false, false, true, false
1889 };
1890
1891 PrepareSFields(sfields);
1892 PrepareBasicBlocks(bbs);
1893 PrepareMIRs(mirs);
1894 PerformGVN();
1895 ASSERT_EQ(arraysize(mirs), value_names_.size());
1896 PerformGVNCodeModifications();
1897 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
1898 for (size_t i = 0u; i != arraysize(mirs); ++i) {
1899 EXPECT_EQ(expected_ignore_null_check[i],
1900 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
1901 }
1902 }
1903
TEST_F(GlobalValueNumberingTest,NullCheckArrays)1904 TEST_F(GlobalValueNumberingTest, NullCheckArrays) {
1905 static const BBDef bbs[] = {
1906 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
1907 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
1908 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
1909 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // 4 is fall-through, 5 is taken.
1910 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)),
1911 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)),
1912 };
1913 static const MIRDef mirs[] = {
1914 DEF_AGET(3, Instruction::AGET_OBJECT, 0u, 100u, 102u),
1915 DEF_AGET(3, Instruction::AGET_OBJECT, 1u, 100u, 103u),
1916 DEF_AGET(3, Instruction::AGET_OBJECT, 2u, 101u, 102u),
1917 DEF_IFZ(3, Instruction::IF_NEZ, 0u), // Null-check for field #0 for taken.
1918 DEF_UNIQUE_REF(4, Instruction::NEW_ARRAY, 4u),
1919 DEF_APUT(4, Instruction::APUT_OBJECT, 4u, 100u, 102u),
1920 DEF_APUT(4, Instruction::APUT_OBJECT, 4u, 100u, 103u),
1921 DEF_APUT(4, Instruction::APUT_OBJECT, 4u, 101u, 102u),
1922 DEF_AGET(5, Instruction::AGET_OBJECT, 8u, 100u, 102u), // Null-checked, IF_NEZ/NEW_ARRAY.
1923 DEF_AGET(5, Instruction::AGET_OBJECT, 9u, 100u, 103u), // Not null-checked, -/NEW_ARRAY.
1924 DEF_AGET(5, Instruction::AGET_OBJECT, 10u, 101u, 102u), // Not null-checked, -/NEW_ARRAY.
1925 DEF_CONST(5, Instruction::CONST, 11u, 0),
1926 DEF_AGET(5, Instruction::AGET, 12u, 8u, 11u), // Null-check eliminated.
1927 DEF_AGET(5, Instruction::AGET, 13u, 9u, 11u), // Null-check kept.
1928 DEF_AGET(5, Instruction::AGET, 14u, 10u, 11u), // Null-check kept.
1929 };
1930 static const bool expected_ignore_null_check[] = {
1931 false, true, false, false, // BB #3; unimportant.
1932 false, true, true, true, // BB #4; unimportant.
1933 true, true, true, false, true, false, false, // BB #5; only the last three are important.
1934 };
1935
1936 PrepareBasicBlocks(bbs);
1937 PrepareMIRs(mirs);
1938 PerformGVN();
1939 ASSERT_EQ(arraysize(mirs), value_names_.size());
1940 PerformGVNCodeModifications();
1941 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
1942 for (size_t i = 0u; i != arraysize(mirs); ++i) {
1943 EXPECT_EQ(expected_ignore_null_check[i],
1944 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
1945 }
1946 }
1947
TEST_F(GlobalValueNumberingTestDiamond,RangeCheckArrays)1948 TEST_F(GlobalValueNumberingTestDiamond, RangeCheckArrays) {
1949 // NOTE: We don't merge range checks when we merge value names for Phis or memory locations.
1950 static const MIRDef mirs[] = {
1951 DEF_AGET(4, Instruction::AGET, 0u, 100u, 101u),
1952 DEF_AGET(5, Instruction::AGET, 1u, 100u, 101u),
1953 DEF_APUT(6, Instruction::APUT, 2u, 100u, 101u),
1954
1955 DEF_AGET(4, Instruction::AGET, 3u, 200u, 201u),
1956 DEF_AGET(5, Instruction::AGET, 4u, 200u, 202u),
1957 DEF_APUT(6, Instruction::APUT, 5u, 200u, 201u),
1958
1959 DEF_AGET(4, Instruction::AGET, 6u, 300u, 302u),
1960 DEF_AGET(5, Instruction::AGET, 7u, 301u, 302u),
1961 DEF_APUT(6, Instruction::APUT, 8u, 300u, 302u),
1962 };
1963 static const bool expected_ignore_null_check[] = {
1964 false, false, true,
1965 false, false, true,
1966 false, false, false,
1967 };
1968 static const bool expected_ignore_range_check[] = {
1969 false, false, true,
1970 false, false, false,
1971 false, false, false,
1972 };
1973
1974 PrepareMIRs(mirs);
1975 PerformGVN();
1976 ASSERT_EQ(arraysize(mirs), value_names_.size());
1977 PerformGVNCodeModifications();
1978 ASSERT_EQ(arraysize(expected_ignore_null_check), mir_count_);
1979 ASSERT_EQ(arraysize(expected_ignore_range_check), mir_count_);
1980 for (size_t i = 0u; i != arraysize(mirs); ++i) {
1981 EXPECT_EQ(expected_ignore_null_check[i],
1982 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
1983 EXPECT_EQ(expected_ignore_range_check[i],
1984 (mirs_[i].optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0) << i;
1985 }
1986 }
1987
TEST_F(GlobalValueNumberingTestDiamond,MergeSameValueInDifferentMemoryLocations)1988 TEST_F(GlobalValueNumberingTestDiamond, MergeSameValueInDifferentMemoryLocations) {
1989 static const IFieldDef ifields[] = {
1990 { 0u, 1u, 0u, false, kDexMemAccessWord },
1991 { 1u, 1u, 1u, false, kDexMemAccessWord },
1992 };
1993 static const SFieldDef sfields[] = {
1994 { 0u, 1u, 0u, false, kDexMemAccessWord },
1995 { 1u, 1u, 1u, false, kDexMemAccessWord },
1996 };
1997 static const MIRDef mirs[] = {
1998 DEF_UNIQUE_REF(3, Instruction::NEW_INSTANCE, 100u),
1999 DEF_UNIQUE_REF(3, Instruction::NEW_ARRAY, 200u),
2000 DEF_CONST(4, Instruction::CONST, 2u, 1000),
2001 DEF_IPUT(4, Instruction::IPUT, 2u, 100u, 0u),
2002 DEF_IPUT(4, Instruction::IPUT, 2u, 100u, 1u),
2003 DEF_IPUT(4, Instruction::IPUT, 2u, 101u, 0u),
2004 DEF_APUT(4, Instruction::APUT, 2u, 200u, 202u),
2005 DEF_APUT(4, Instruction::APUT, 2u, 200u, 203u),
2006 DEF_APUT(4, Instruction::APUT, 2u, 201u, 202u),
2007 DEF_APUT(4, Instruction::APUT, 2u, 201u, 203u),
2008 DEF_SPUT(4, Instruction::SPUT, 2u, 0u),
2009 DEF_SPUT(4, Instruction::SPUT, 2u, 1u),
2010 DEF_CONST(5, Instruction::CONST, 12u, 2000),
2011 DEF_IPUT(5, Instruction::IPUT, 12u, 100u, 0u),
2012 DEF_IPUT(5, Instruction::IPUT, 12u, 100u, 1u),
2013 DEF_IPUT(5, Instruction::IPUT, 12u, 101u, 0u),
2014 DEF_APUT(5, Instruction::APUT, 12u, 200u, 202u),
2015 DEF_APUT(5, Instruction::APUT, 12u, 200u, 203u),
2016 DEF_APUT(5, Instruction::APUT, 12u, 201u, 202u),
2017 DEF_APUT(5, Instruction::APUT, 12u, 201u, 203u),
2018 DEF_SPUT(5, Instruction::SPUT, 12u, 0u),
2019 DEF_SPUT(5, Instruction::SPUT, 12u, 1u),
2020 DEF_PHI2(6, 22u, 2u, 12u),
2021 DEF_IGET(6, Instruction::IGET, 23u, 100u, 0u),
2022 DEF_IGET(6, Instruction::IGET, 24u, 100u, 1u),
2023 DEF_IGET(6, Instruction::IGET, 25u, 101u, 0u),
2024 DEF_AGET(6, Instruction::AGET, 26u, 200u, 202u),
2025 DEF_AGET(6, Instruction::AGET, 27u, 200u, 203u),
2026 DEF_AGET(6, Instruction::AGET, 28u, 201u, 202u),
2027 DEF_AGET(6, Instruction::AGET, 29u, 201u, 203u),
2028 DEF_SGET(6, Instruction::SGET, 30u, 0u),
2029 DEF_SGET(6, Instruction::SGET, 31u, 1u),
2030 };
2031 PrepareIFields(ifields);
2032 PrepareSFields(sfields);
2033 PrepareMIRs(mirs);
2034 PerformGVN();
2035 ASSERT_EQ(arraysize(mirs), value_names_.size());
2036 EXPECT_NE(value_names_[2], value_names_[12]);
2037 EXPECT_NE(value_names_[2], value_names_[22]);
2038 EXPECT_NE(value_names_[12], value_names_[22]);
2039 for (size_t i = 23; i != arraysize(mirs); ++i) {
2040 EXPECT_EQ(value_names_[22], value_names_[i]) << i;
2041 }
2042 }
2043
TEST_F(GlobalValueNumberingTest,InfiniteLocationLoop)2044 TEST_F(GlobalValueNumberingTest, InfiniteLocationLoop) {
2045 // This is a pattern that lead to an infinite loop during the GVN development. This has been
2046 // fixed by rewriting the merging of AliasingValues to merge only locations read from or
2047 // written to in each incoming LVN rather than merging all locations read from or written to
2048 // in any incoming LVN. It also showed up only when the GVN used the DFS ordering instead of
2049 // the "topological" ordering but, since the "topological" ordering is not really topological
2050 // when there are cycles and an optimizing Java compiler (or a tool like proguard) could
2051 // theoretically create any sort of flow graph, this could have shown up in real code.
2052 //
2053 // While we were merging all the locations:
2054 // The first time the Phi evaluates to the same value name as CONST 0u. After the second
2055 // evaluation, when the BB #9 has been processed, the Phi receives its own value name.
2056 // However, the index from the first evaluation keeps disappearing and reappearing in the
2057 // LVN's aliasing_array_value_map_'s load_value_map for BBs #9, #4, #5, #7 because of the
2058 // DFS ordering of LVN evaluation.
2059 static const IFieldDef ifields[] = {
2060 { 0u, 1u, 0u, false, kDexMemAccessObject },
2061 };
2062 static const BBDef bbs[] = {
2063 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
2064 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
2065 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(4)),
2066 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
2067 DEF_BB(kDalvikByteCode, DEF_SUCC2(5, 2), DEF_PRED2(3, 9)),
2068 DEF_BB(kDalvikByteCode, DEF_SUCC2(6, 7), DEF_PRED1(4)),
2069 DEF_BB(kDalvikByteCode, DEF_SUCC1(9), DEF_PRED1(5)),
2070 DEF_BB(kDalvikByteCode, DEF_SUCC2(8, 9), DEF_PRED1(5)),
2071 DEF_BB(kDalvikByteCode, DEF_SUCC1(9), DEF_PRED1(7)),
2072 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED3(6, 7, 8)),
2073 };
2074 static const MIRDef mirs[] = {
2075 DEF_CONST(3, Instruction::CONST, 0u, 0),
2076 DEF_PHI2(4, 1u, 0u, 10u),
2077 DEF_INVOKE1(6, Instruction::INVOKE_STATIC, 100u),
2078 DEF_IGET(6, Instruction::IGET_OBJECT, 3u, 100u, 0u),
2079 DEF_CONST(6, Instruction::CONST, 4u, 1000),
2080 DEF_APUT(6, Instruction::APUT, 4u, 3u, 1u), // Index is Phi 1u.
2081 DEF_INVOKE1(8, Instruction::INVOKE_STATIC, 100u),
2082 DEF_IGET(8, Instruction::IGET_OBJECT, 7u, 100u, 0u),
2083 DEF_CONST(8, Instruction::CONST, 8u, 2000),
2084 DEF_APUT(8, Instruction::APUT, 9u, 7u, 1u), // Index is Phi 1u.
2085 DEF_CONST(9, Instruction::CONST, 10u, 3000),
2086 };
2087 PrepareIFields(ifields);
2088 PrepareBasicBlocks(bbs);
2089 PrepareMIRs(mirs);
2090 // Using DFS order for this test. The GVN result should not depend on the used ordering
2091 // once the GVN actually converges. But creating a test for this convergence issue with
2092 // the topological ordering could be a very challenging task.
2093 PerformPreOrderDfsGVN();
2094 }
2095
TEST_F(GlobalValueNumberingTestTwoConsecutiveLoops,IFieldAndPhi)2096 TEST_F(GlobalValueNumberingTestTwoConsecutiveLoops, IFieldAndPhi) {
2097 static const IFieldDef ifields[] = {
2098 { 0u, 1u, 0u, false, kDexMemAccessObject },
2099 };
2100 static const MIRDef mirs[] = {
2101 DEF_MOVE(3, Instruction::MOVE_OBJECT, 0u, 100u),
2102 DEF_IPUT(3, Instruction::IPUT_OBJECT, 0u, 200u, 0u),
2103 DEF_PHI2(4, 2u, 0u, 3u),
2104 DEF_MOVE(5, Instruction::MOVE_OBJECT, 3u, 300u),
2105 DEF_IPUT(5, Instruction::IPUT_OBJECT, 3u, 200u, 0u),
2106 DEF_MOVE(6, Instruction::MOVE_OBJECT, 5u, 2u),
2107 DEF_IGET(6, Instruction::IGET_OBJECT, 6u, 200u, 0u),
2108 DEF_MOVE(7, Instruction::MOVE_OBJECT, 7u, 5u),
2109 DEF_IGET(7, Instruction::IGET_OBJECT, 8u, 200u, 0u),
2110 DEF_MOVE(8, Instruction::MOVE_OBJECT, 9u, 5u),
2111 DEF_IGET(8, Instruction::IGET_OBJECT, 10u, 200u, 0u),
2112 DEF_MOVE(9, Instruction::MOVE_OBJECT, 11u, 5u),
2113 DEF_IGET(9, Instruction::IGET_OBJECT, 12u, 200u, 0u),
2114 };
2115
2116 PrepareIFields(ifields);
2117 PrepareMIRs(mirs);
2118 PerformGVN();
2119 ASSERT_EQ(arraysize(mirs), value_names_.size());
2120 EXPECT_NE(value_names_[0], value_names_[3]);
2121 EXPECT_NE(value_names_[0], value_names_[2]);
2122 EXPECT_NE(value_names_[3], value_names_[2]);
2123 EXPECT_EQ(value_names_[2], value_names_[5]);
2124 EXPECT_EQ(value_names_[5], value_names_[6]);
2125 EXPECT_EQ(value_names_[5], value_names_[7]);
2126 EXPECT_EQ(value_names_[5], value_names_[8]);
2127 EXPECT_EQ(value_names_[5], value_names_[9]);
2128 EXPECT_EQ(value_names_[5], value_names_[10]);
2129 EXPECT_EQ(value_names_[5], value_names_[11]);
2130 EXPECT_EQ(value_names_[5], value_names_[12]);
2131 }
2132
TEST_F(GlobalValueNumberingTestTwoConsecutiveLoops,NullCheck)2133 TEST_F(GlobalValueNumberingTestTwoConsecutiveLoops, NullCheck) {
2134 static const IFieldDef ifields[] = {
2135 { 0u, 1u, 0u, false, kDexMemAccessObject },
2136 };
2137 static const SFieldDef sfields[] = {
2138 { 0u, 1u, 0u, false, kDexMemAccessObject },
2139 };
2140 static const MIRDef mirs[] = {
2141 DEF_MOVE(3, Instruction::MOVE_OBJECT, 0u, 100u),
2142 DEF_IGET(3, Instruction::IGET_OBJECT, 1u, 200u, 0u),
2143 DEF_SGET(3, Instruction::SGET_OBJECT, 2u, 0u),
2144 DEF_AGET(3, Instruction::AGET_OBJECT, 3u, 300u, 201u),
2145 DEF_PHI2(4, 4u, 0u, 8u),
2146 DEF_IGET(5, Instruction::IGET_OBJECT, 5u, 200u, 0u),
2147 DEF_SGET(5, Instruction::SGET_OBJECT, 6u, 0u),
2148 DEF_AGET(5, Instruction::AGET_OBJECT, 7u, 300u, 201u),
2149 DEF_MOVE(5, Instruction::MOVE_OBJECT, 8u, 400u),
2150 DEF_IPUT(5, Instruction::IPUT_OBJECT, 4u, 200u, 0u), // PUT the Phi 4u.
2151 DEF_SPUT(5, Instruction::SPUT_OBJECT, 4u, 0u), // PUT the Phi 4u.
2152 DEF_APUT(5, Instruction::APUT_OBJECT, 4u, 300u, 201u), // PUT the Phi 4u.
2153 DEF_MOVE(6, Instruction::MOVE_OBJECT, 12u, 4u),
2154 DEF_IGET(6, Instruction::IGET_OBJECT, 13u, 200u, 0u),
2155 DEF_SGET(6, Instruction::SGET_OBJECT, 14u, 0u),
2156 DEF_AGET(6, Instruction::AGET_OBJECT, 15u, 300u, 201u),
2157 DEF_AGET(6, Instruction::AGET_OBJECT, 16u, 12u, 600u),
2158 DEF_AGET(6, Instruction::AGET_OBJECT, 17u, 13u, 600u),
2159 DEF_AGET(6, Instruction::AGET_OBJECT, 18u, 14u, 600u),
2160 DEF_AGET(6, Instruction::AGET_OBJECT, 19u, 15u, 600u),
2161 DEF_MOVE(8, Instruction::MOVE_OBJECT, 20u, 12u),
2162 DEF_IGET(8, Instruction::IGET_OBJECT, 21u, 200u, 0u),
2163 DEF_SGET(8, Instruction::SGET_OBJECT, 22u, 0u),
2164 DEF_AGET(8, Instruction::AGET_OBJECT, 23u, 300u, 201u),
2165 DEF_AGET(8, Instruction::AGET_OBJECT, 24u, 12u, 600u),
2166 DEF_AGET(8, Instruction::AGET_OBJECT, 25u, 13u, 600u),
2167 DEF_AGET(8, Instruction::AGET_OBJECT, 26u, 14u, 600u),
2168 DEF_AGET(8, Instruction::AGET_OBJECT, 27u, 15u, 600u),
2169 DEF_MOVE(9, Instruction::MOVE_OBJECT, 28u, 12u),
2170 DEF_IGET(9, Instruction::IGET_OBJECT, 29u, 200u, 0u),
2171 DEF_SGET(9, Instruction::SGET_OBJECT, 30u, 0u),
2172 DEF_AGET(9, Instruction::AGET_OBJECT, 31u, 300u, 201u),
2173 DEF_AGET(9, Instruction::AGET_OBJECT, 32u, 12u, 600u),
2174 DEF_AGET(9, Instruction::AGET_OBJECT, 33u, 13u, 600u),
2175 DEF_AGET(9, Instruction::AGET_OBJECT, 34u, 14u, 600u),
2176 DEF_AGET(9, Instruction::AGET_OBJECT, 35u, 15u, 600u),
2177 };
2178 static const bool expected_ignore_null_check[] = {
2179 false, false, false, false, // BB #3.
2180 false, true, false, true, false, true, false, true, // BBs #4 and #5.
2181 false, true, false, true, false, false, false, false, // BB #6.
2182 false, true, false, true, true, true, true, true, // BB #7.
2183 false, true, false, true, true, true, true, true, // BB #8.
2184 };
2185 static const bool expected_ignore_range_check[] = {
2186 false, false, false, false, // BB #3.
2187 false, false, false, true, false, false, false, true, // BBs #4 and #5.
2188 false, false, false, true, false, false, false, false, // BB #6.
2189 false, false, false, true, true, true, true, true, // BB #7.
2190 false, false, false, true, true, true, true, true, // BB #8.
2191 };
2192
2193 PrepareIFields(ifields);
2194 PrepareSFields(sfields);
2195 PrepareMIRs(mirs);
2196 PerformGVN();
2197 ASSERT_EQ(arraysize(mirs), value_names_.size());
2198 EXPECT_NE(value_names_[0], value_names_[4]);
2199 EXPECT_NE(value_names_[1], value_names_[5]);
2200 EXPECT_NE(value_names_[2], value_names_[6]);
2201 EXPECT_NE(value_names_[3], value_names_[7]);
2202 EXPECT_NE(value_names_[4], value_names_[8]);
2203 EXPECT_EQ(value_names_[4], value_names_[12]);
2204 EXPECT_EQ(value_names_[5], value_names_[13]);
2205 EXPECT_EQ(value_names_[6], value_names_[14]);
2206 EXPECT_EQ(value_names_[7], value_names_[15]);
2207 EXPECT_EQ(value_names_[12], value_names_[20]);
2208 EXPECT_EQ(value_names_[13], value_names_[21]);
2209 EXPECT_EQ(value_names_[14], value_names_[22]);
2210 EXPECT_EQ(value_names_[15], value_names_[23]);
2211 EXPECT_EQ(value_names_[12], value_names_[28]);
2212 EXPECT_EQ(value_names_[13], value_names_[29]);
2213 EXPECT_EQ(value_names_[14], value_names_[30]);
2214 EXPECT_EQ(value_names_[15], value_names_[31]);
2215 PerformGVNCodeModifications();
2216 for (size_t i = 0u; i != arraysize(mirs); ++i) {
2217 EXPECT_EQ(expected_ignore_null_check[i],
2218 (mirs_[i].optimization_flags & MIR_IGNORE_NULL_CHECK) != 0) << i;
2219 EXPECT_EQ(expected_ignore_range_check[i],
2220 (mirs_[i].optimization_flags & MIR_IGNORE_RANGE_CHECK) != 0) << i;
2221 }
2222 }
2223
TEST_F(GlobalValueNumberingTestTwoNestedLoops,IFieldAndPhi)2224 TEST_F(GlobalValueNumberingTestTwoNestedLoops, IFieldAndPhi) {
2225 static const IFieldDef ifields[] = {
2226 { 0u, 1u, 0u, false, kDexMemAccessObject },
2227 };
2228 static const MIRDef mirs[] = {
2229 DEF_MOVE(3, Instruction::MOVE_OBJECT, 0u, 100u),
2230 DEF_IPUT(3, Instruction::IPUT_OBJECT, 0u, 200u, 0u),
2231 DEF_PHI2(4, 2u, 0u, 11u),
2232 DEF_MOVE(4, Instruction::MOVE_OBJECT, 3u, 2u),
2233 DEF_IGET(4, Instruction::IGET_OBJECT, 4u, 200u, 0u),
2234 DEF_MOVE(5, Instruction::MOVE_OBJECT, 5u, 3u),
2235 DEF_IGET(5, Instruction::IGET_OBJECT, 6u, 200u, 0u),
2236 DEF_MOVE(6, Instruction::MOVE_OBJECT, 7u, 3u),
2237 DEF_IGET(6, Instruction::IGET_OBJECT, 8u, 200u, 0u),
2238 DEF_MOVE(7, Instruction::MOVE_OBJECT, 9u, 3u),
2239 DEF_IGET(7, Instruction::IGET_OBJECT, 10u, 200u, 0u),
2240 DEF_MOVE(7, Instruction::MOVE_OBJECT, 11u, 300u),
2241 DEF_IPUT(7, Instruction::IPUT_OBJECT, 11u, 200u, 0u),
2242 DEF_MOVE(8, Instruction::MOVE_OBJECT, 13u, 3u),
2243 DEF_IGET(8, Instruction::IGET_OBJECT, 14u, 200u, 0u),
2244 };
2245
2246 PrepareIFields(ifields);
2247 PrepareMIRs(mirs);
2248 PerformGVN();
2249 ASSERT_EQ(arraysize(mirs), value_names_.size());
2250 EXPECT_NE(value_names_[0], value_names_[11]);
2251 EXPECT_NE(value_names_[0], value_names_[2]);
2252 EXPECT_NE(value_names_[11], value_names_[2]);
2253 EXPECT_EQ(value_names_[2], value_names_[3]);
2254 EXPECT_EQ(value_names_[3], value_names_[4]);
2255 EXPECT_EQ(value_names_[3], value_names_[5]);
2256 EXPECT_EQ(value_names_[3], value_names_[6]);
2257 EXPECT_EQ(value_names_[3], value_names_[7]);
2258 EXPECT_EQ(value_names_[3], value_names_[8]);
2259 EXPECT_EQ(value_names_[3], value_names_[9]);
2260 EXPECT_EQ(value_names_[3], value_names_[10]);
2261 EXPECT_EQ(value_names_[3], value_names_[13]);
2262 EXPECT_EQ(value_names_[3], value_names_[14]);
2263 }
2264
TEST_F(GlobalValueNumberingTest,NormalPathToCatchEntry)2265 TEST_F(GlobalValueNumberingTest, NormalPathToCatchEntry) {
2266 // When there's an empty catch block, all the exception paths lead to the next block in
2267 // the normal path and we can also have normal "taken" or "fall-through" branches to that
2268 // path. Check that LocalValueNumbering::PruneNonAliasingRefsForCatch() can handle it.
2269 static const BBDef bbs[] = {
2270 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
2271 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
2272 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(5)),
2273 DEF_BB(kDalvikByteCode, DEF_SUCC1(4), DEF_PRED1(1)),
2274 DEF_BB(kDalvikByteCode, DEF_SUCC1(5), DEF_PRED1(3)),
2275 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(3, 4)),
2276 };
2277 static const MIRDef mirs[] = {
2278 DEF_INVOKE1(4, Instruction::INVOKE_STATIC, 100u),
2279 };
2280 PrepareBasicBlocks(bbs);
2281 BasicBlock* catch_handler = cu_.mir_graph->GetBasicBlock(5u);
2282 catch_handler->catch_entry = true;
2283 // Add successor block info to the check block.
2284 BasicBlock* check_bb = cu_.mir_graph->GetBasicBlock(3u);
2285 check_bb->successor_block_list_type = kCatch;
2286 SuccessorBlockInfo* successor_block_info = reinterpret_cast<SuccessorBlockInfo*>
2287 (cu_.arena.Alloc(sizeof(SuccessorBlockInfo), kArenaAllocSuccessor));
2288 successor_block_info->block = catch_handler->id;
2289 check_bb->successor_blocks.push_back(successor_block_info);
2290 BasicBlock* merge_block = cu_.mir_graph->GetBasicBlock(4u);
2291 std::swap(merge_block->taken, merge_block->fall_through);
2292 PrepareMIRs(mirs);
2293 PerformGVN();
2294 }
2295
TEST_F(GlobalValueNumberingTestDiamond,DivZeroCheckDiamond)2296 TEST_F(GlobalValueNumberingTestDiamond, DivZeroCheckDiamond) {
2297 static const MIRDef mirs[] = {
2298 DEF_BINOP(3u, Instruction::DIV_INT, 1u, 20u, 21u),
2299 DEF_BINOP(3u, Instruction::DIV_INT, 2u, 24u, 21u),
2300 DEF_BINOP(3u, Instruction::DIV_INT, 3u, 20u, 23u),
2301 DEF_BINOP(4u, Instruction::DIV_INT, 4u, 24u, 22u),
2302 DEF_BINOP(4u, Instruction::DIV_INT, 9u, 24u, 25u),
2303 DEF_BINOP(5u, Instruction::DIV_INT, 5u, 24u, 21u),
2304 DEF_BINOP(5u, Instruction::DIV_INT, 10u, 24u, 26u),
2305 DEF_PHI2(6u, 27u, 25u, 26u),
2306 DEF_BINOP(6u, Instruction::DIV_INT, 12u, 20u, 27u),
2307 DEF_BINOP(6u, Instruction::DIV_INT, 6u, 24u, 21u),
2308 DEF_BINOP(6u, Instruction::DIV_INT, 7u, 20u, 23u),
2309 DEF_BINOP(6u, Instruction::DIV_INT, 8u, 20u, 22u),
2310 };
2311
2312 static const bool expected_ignore_div_zero_check[] = {
2313 false, // New divisor seen.
2314 true, // Eliminated since it has first divisor as first one.
2315 false, // New divisor seen.
2316 false, // New divisor seen.
2317 false, // New divisor seen.
2318 true, // Eliminated in dominating block.
2319 false, // New divisor seen.
2320 false, // Phi node.
2321 true, // Eliminated on both sides of diamond and merged via phi.
2322 true, // Eliminated in dominating block.
2323 true, // Eliminated in dominating block.
2324 false, // Only eliminated on one path of diamond.
2325 };
2326
2327 PrepareMIRs(mirs);
2328 PerformGVN();
2329 PerformGVNCodeModifications();
2330 ASSERT_EQ(arraysize(expected_ignore_div_zero_check), mir_count_);
2331 for (size_t i = 0u; i != mir_count_; ++i) {
2332 int expected = expected_ignore_div_zero_check[i] ? MIR_IGNORE_DIV_ZERO_CHECK : 0u;
2333 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i;
2334 }
2335 }
2336
TEST_F(GlobalValueNumberingTestDiamond,CheckCastDiamond)2337 TEST_F(GlobalValueNumberingTestDiamond, CheckCastDiamond) {
2338 static const MIRDef mirs[] = {
2339 DEF_UNOP(3u, Instruction::INSTANCE_OF, 0u, 100u),
2340 DEF_UNOP(3u, Instruction::INSTANCE_OF, 1u, 200u),
2341 DEF_IFZ(3u, Instruction::IF_NEZ, 0u),
2342 DEF_INVOKE1(4u, Instruction::CHECK_CAST, 100u),
2343 DEF_INVOKE1(5u, Instruction::CHECK_CAST, 100u),
2344 DEF_INVOKE1(5u, Instruction::CHECK_CAST, 200u),
2345 DEF_INVOKE1(5u, Instruction::CHECK_CAST, 100u),
2346 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 100u),
2347 };
2348
2349 static const bool expected_ignore_check_cast[] = {
2350 false, // instance-of
2351 false, // instance-of
2352 false, // if-nez
2353 false, // Not eliminated, fall-through branch.
2354 true, // Eliminated.
2355 false, // Not eliminated, different value.
2356 false, // Not eliminated, different type.
2357 false, // Not eliminated, bottom block.
2358 };
2359
2360 PrepareMIRs(mirs);
2361 mirs_[0].dalvikInsn.vC = 1234; // type for instance-of
2362 mirs_[1].dalvikInsn.vC = 1234; // type for instance-of
2363 mirs_[3].dalvikInsn.vB = 1234; // type for check-cast
2364 mirs_[4].dalvikInsn.vB = 1234; // type for check-cast
2365 mirs_[5].dalvikInsn.vB = 1234; // type for check-cast
2366 mirs_[6].dalvikInsn.vB = 4321; // type for check-cast
2367 mirs_[7].dalvikInsn.vB = 1234; // type for check-cast
2368 PerformGVN();
2369 PerformGVNCodeModifications();
2370 ASSERT_EQ(arraysize(expected_ignore_check_cast), mir_count_);
2371 for (size_t i = 0u; i != mir_count_; ++i) {
2372 int expected = expected_ignore_check_cast[i] ? MIR_IGNORE_CHECK_CAST : 0u;
2373 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i;
2374 }
2375 }
2376
TEST_F(GlobalValueNumberingTest,CheckCastDominators)2377 TEST_F(GlobalValueNumberingTest, CheckCastDominators) {
2378 const BBDef bbs[] = {
2379 DEF_BB(kNullBlock, DEF_SUCC0(), DEF_PRED0()),
2380 DEF_BB(kEntryBlock, DEF_SUCC1(3), DEF_PRED0()),
2381 DEF_BB(kExitBlock, DEF_SUCC0(), DEF_PRED1(7)),
2382 DEF_BB(kDalvikByteCode, DEF_SUCC2(4, 5), DEF_PRED1(1)), // Block #3, top of the diamond.
2383 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(3)), // Block #4, left side.
2384 DEF_BB(kDalvikByteCode, DEF_SUCC1(6), DEF_PRED1(3)), // Block #5, right side.
2385 DEF_BB(kDalvikByteCode, DEF_SUCC1(7), DEF_PRED1(5)), // Block #6, right side.
2386 DEF_BB(kDalvikByteCode, DEF_SUCC1(2), DEF_PRED2(4, 6)), // Block #7, bottom.
2387 };
2388 static const MIRDef mirs[] = {
2389 DEF_UNOP(3u, Instruction::INSTANCE_OF, 0u, 100u),
2390 DEF_UNOP(3u, Instruction::INSTANCE_OF, 1u, 200u),
2391 DEF_IFZ(3u, Instruction::IF_NEZ, 0u),
2392 DEF_INVOKE1(4u, Instruction::CHECK_CAST, 100u),
2393 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 100u),
2394 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 200u),
2395 DEF_INVOKE1(6u, Instruction::CHECK_CAST, 100u),
2396 DEF_INVOKE1(7u, Instruction::CHECK_CAST, 100u),
2397 };
2398
2399 static const bool expected_ignore_check_cast[] = {
2400 false, // instance-of
2401 false, // instance-of
2402 false, // if-nez
2403 false, // Not eliminated, fall-through branch.
2404 true, // Eliminated.
2405 false, // Not eliminated, different value.
2406 false, // Not eliminated, different type.
2407 false, // Not eliminated, bottom block.
2408 };
2409
2410 PrepareBasicBlocks(bbs);
2411 PrepareMIRs(mirs);
2412 mirs_[0].dalvikInsn.vC = 1234; // type for instance-of
2413 mirs_[1].dalvikInsn.vC = 1234; // type for instance-of
2414 mirs_[3].dalvikInsn.vB = 1234; // type for check-cast
2415 mirs_[4].dalvikInsn.vB = 1234; // type for check-cast
2416 mirs_[5].dalvikInsn.vB = 1234; // type for check-cast
2417 mirs_[6].dalvikInsn.vB = 4321; // type for check-cast
2418 mirs_[7].dalvikInsn.vB = 1234; // type for check-cast
2419 PerformGVN();
2420 PerformGVNCodeModifications();
2421 ASSERT_EQ(arraysize(expected_ignore_check_cast), mir_count_);
2422 for (size_t i = 0u; i != mir_count_; ++i) {
2423 int expected = expected_ignore_check_cast[i] ? MIR_IGNORE_CHECK_CAST : 0u;
2424 EXPECT_EQ(expected, mirs_[i].optimization_flags) << i;
2425 }
2426 }
2427
2428 } // namespace art
2429