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