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